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.
#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;
}
For (i, 1, n) {
cin >> a[i].x;
a[i].y = i;
}
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 (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
*/
Auto comment: topic has been updated by Coder_Fang (previous revision, new revision, compare).