About today's CF 2E

Revision en1, by Coder_Fang, 2023-10-09 19:57:13

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 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 */

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Coder_Fang 2023-10-09 20:02:35 119
en3 English Coder_Fang 2023-10-09 19:59:17 48
en2 English Coder_Fang 2023-10-09 19:57:43 13
en1 English Coder_Fang 2023-10-09 19:57:13 2247 Initial revision (published)