I used dp,2^m*m+n*m,but Wrong Answer on test 9,what a pity!↵
Could you help me find where I do mistakes in my code,thanks.↵
↵
```cpp↵
#include <bits/stdc++.h>↵
#define int long long↵
#define mp make_pair↵
#define For(i, a, b) for (int i = (a); i <= (b); i ++)↵
#define foR(i, a, b) for (int i = (a); i >= (b); i --)↵
using namespace std;↵
int n, m;↵
int c[200005];↵
int f[1 << 20], pre[21];↵
int come[1 << 20];↵
int comee[1 << 20], doo[1 << 20];↵
int p[21][200005];↵
pair <int, int> cc[200005];↵
struct Node {int x, y;}a[200005], b[200005];↵
bool cmp (Node n1, Node n2) {return n1.x < n2.x;}↵
vector <int> ans[200005];↵
void init () {↵
For (i, 1, m) {↵
For (j, 1, n + 1) c[j] = 1000000000;↵
For (j, 1, n) {↵
c[j] = j + (b[i].x — 1) / a[j].x;↵
}↵
foR (j, n, 1) c[j] = min (c[j], c[j + 1]);↵
For (j, 1, n) p[i][j] = c[j];↵
}↵
}↵
void solve () {↵
For (i, 0, 19) pre[i] = 1 << i;↵
memset (f, 0x3f, sizeof f);↵
cin >> n >> m;↵
if (n < m) {↵
cout << "NO";↵
return;↵
}↵
bool ff = false;↵
For (i, 1, n) {↵
cin >> a[i].x;↵
a[i].y = i;↵
}↵
if (a[1].x == 66844) {↵
ff = true;↵
}↵
For (i, 1, m) {↵
cin >> b[i].x;↵
b[i].y = i;↵
}↵
sort (a + 1, a + n + 1, cmp);↵
sort (b + 1, b + m + 1, cmp);↵
init ();↵
f[0] = 0;↵
For (i, 1, (1 << m) — 1) {↵
For (j, 0, m — 1) {↵
if (i & pre[j]) {↵
int k = i ^ pre[j];↵
if (f[k] < n && p[j + 1][f[k] + 1] <= n) {↵
f[i] = p[j + 1][f[k] + 1];↵
come[i] = k;↵
cc[i] = mp (f[k] + 1, p[j + 1][f[k] + 1]);↵
doo[i] = j + 1;↵
}↵
}↵
}↵
}↵
if (ff) {↵
cout << f[(1 << m) — 1];↵
return;↵
}↵
if (f[(1 << m) — 1] <= n) cout << "Yes" << '\n';↵
else {↵
cout << "No";↵
return;↵
}↵
int st = (1 << m) — 1;↵
while (st) {↵
int len = 0, sum = 0;↵
foR (i, cc[st].second, cc[st].first) {↵
++ len;↵
sum += a[i].x;↵
ans[b[doo[st]].y].push_back (a[i].y);↵
if (a[i].x * len >= b[doo[st] ].x) break;↵
}↵
st = come[st];↵
}↵
For (i, 1, m) {↵
cout << ans[i].size () << ' ';↵
for (int j : ans[i]) cout << j << ' ';↵
cout << '\n';↵
}↵
}↵
signed main () {↵
int _ = 1;↵
// cin >> _;↵
while (_ --) {↵
solve ();↵
cout << '\n';↵
}↵
return 0;↵
}↵
/*↵
5 3↵
1 4 5 6 100↵
1 12 50↵
*/↵
```
Could you help me find where I do mistakes in my code,thanks.↵
↵
```cpp↵
#include <bits/stdc++.h>↵
#define int long long↵
#define mp make_pair↵
#define For(i, a, b) for (int i = (a); i <= (b); i ++)↵
#define foR(i, a, b) for (int i = (a); i >= (b); i --)↵
using namespace std;↵
int n, m;↵
int c[200005];↵
int f[1 << 20], pre[21];↵
int come[1 << 20];↵
int comee[1 << 20], doo[1 << 20];↵
int p[21][200005];↵
pair <int, int> cc[200005];↵
struct Node {int x, y;}a[200005], b[200005];↵
bool cmp (Node n1, Node n2) {return n1.x < n2.x;}↵
vector <int> ans[200005];↵
void init () {↵
For (i, 1, m) {↵
For (j, 1, n + 1) c[j] = 1000000000;↵
For (j, 1, n) {↵
c[j] = j + (b[i].x — 1) / a[j].x;↵
}↵
foR (j, n, 1) c[j] = min (c[j], c[j + 1]);↵
For (j, 1, n) p[i][j] = c[j];↵
}↵
}↵
void solve () {↵
For (i, 0, 19) pre[i] = 1 << i;↵
memset (f, 0x3f, sizeof f);↵
cin >> n >> m;↵
if (n < m) {↵
cout << "NO";↵
return;↵
}↵
bool ff = false;↵
For (i, 1, n) {↵
cin >> a[i].x;↵
a[i].y = i;↵
}↵
if (a[1].x == 66844) {↵
ff = true;↵
}↵
For (i, 1, m) {↵
cin >> b[i].x;↵
b[i].y = i;↵
}↵
sort (a + 1, a + n + 1, cmp);↵
sort (b + 1, b + m + 1, cmp);↵
init ();↵
f[0] = 0;↵
For (i, 1, (1 << m) — 1) {↵
For (j, 0, m — 1) {↵
if (i & pre[j]) {↵
int k = i ^ pre[j];↵
if (f[k] < n && p[j + 1][f[k] + 1] <= n) {↵
f[i] = p[j + 1][f[k] + 1];↵
come[i] = k;↵
cc[i] = mp (f[k] + 1, p[j + 1][f[k] + 1]);↵
doo[i] = j + 1;↵
}↵
}↵
}↵
}↵
if (ff) {↵
cout << f[(1 << m) — 1];↵
return;↵
}↵
if (f[(1 << m) — 1] <= n) cout << "Yes" << '\n';↵
else {↵
cout << "No";↵
return;↵
}↵
int st = (1 << m) — 1;↵
while (st) {↵
int len = 0, sum = 0;↵
foR (i, cc[st].second, cc[st].first) {↵
++ len;↵
sum += a[i].x;↵
ans[b[doo[st]].y].push_back (a[i].y);↵
if (a[i].x * len >= b[doo[st] ].x) break;↵
}↵
st = come[st];↵
}↵
For (i, 1, m) {↵
cout << ans[i].size () << ' ';↵
for (int j : ans[i]) cout << j << ' ';↵
cout << '\n';↵
}↵
}↵
signed main () {↵
int _ = 1;↵
// cin >> _;↵
while (_ --) {↵
solve ();↵
cout << '\n';↵
}↵
return 0;↵
}↵
/*↵
5 3↵
1 4 5 6 100↵
1 12 50↵
*/↵
```
