Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

Coder_Fang's blog

By Coder_Fang, history, 14 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • -9
  • Vote: I do not like it