Submission #789309

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
789309	2023-07-21T09:06:46 Z	박영우(#10045)	Cookies (JOI23_cookies)	C++17	63 / 100	54 ms	1748 KB

#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 600
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int A[MAX];
int cnt[MAX];
int B[MAX];
int dp[MAX][MAX];
vector<int> ansv;
int N, M;
void print() {
	vector<int> v;
	vector<vector<int>> res;
	int i;
	for (i = 1; i <= N; i++) v.push_back(i);
	for (auto b : ansv) {
		vector<int> nv;
		sort(v.begin(), v.end(), [&](int i, int j) {return A[i] > A[j]; });
		for (i = 0; i < b; i++) {
			nv.push_back(v[i]);
			A[v[i]]--;
		}
		res.push_back(nv);
	}
	for (i = 1; i <= N; i++) if (A[i]) {
		cout << -1 << ln;
		exit(0);
	}
	cout << res.size() << ln;
	for (auto& v : res) {
		cout << v.size() << bb;
		for (auto x : v) cout << x << bb;
		cout << ln;
	}
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> N;
	int i, j, k;
	int S = 0;
	for (i = 1; i <= N; i++) {
		cin >> A[i];
		S += A[i];
		for (j = 1; j <= A[i]; j++) cnt[j]++;
	}
	cin >> M;
	for (i = 1; i <= M; i++) cin >> B[i];
	if (M == 1) {
		if (S % B[1]) {
			cout << -1 << ln;
			return 0;
		}
		ansv = vector<int>(S / B[1], B[1]);
		print();
		return 0;
	}
	for (i = 1; i <= S; i++) cnt[i] += cnt[i - 1];
	memset(dp, -1, sizeof(dp));
	dp[0][0] = 1e9;
	for (i = 1; i <= S; i++) {
		for (j = 0; j <= cnt[i - 1]; j++) {
			if (!~dp[i - 1][j]) continue;
			for (k = 1; k <= M; k++) if (j + B[k] <= cnt[i] && B[k] <= dp[i - 1][j]) dp[i][j + B[k]] = max(dp[i][j + B[k]], B[k]);
		}
	}
	int loc;
	for (i = 1; i <= S; i++) if (~dp[i][S]) break;
	loc = i;
	if (loc > S) {
		cout << -1;
		return 0;
	}
	int n = S;
	for (i = loc; i >= 1; i--) {
		int path = dp[i][n];
		assert(path != -1);
		n -= path;
		if (path) ansv.push_back(path);
	}
	sort(ansv.begin(), ansv.end(), [&](int i, int j) {return i > j; });
	print();
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1620 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	1620 KB	Output is correct
6	Correct	1 ms	1620 KB	Output is correct
7	Correct	1 ms	1620 KB	Output is correct
8	Correct	4 ms	376 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	54 ms	1716 KB	Output is correct
11	Correct	1 ms	1620 KB	Output is correct
12	Correct	4 ms	1732 KB	Output is correct
13	Correct	4 ms	1748 KB	Output is correct
14	Correct	2 ms	1620 KB	Output is correct
15	Correct	3 ms	1748 KB	Output is correct
16	Correct	2 ms	1748 KB	Output is correct
17	Correct	1 ms	1620 KB	Output is correct
18	Correct	2 ms	1620 KB	Output is correct
19	Correct	1 ms	1620 KB	Output is correct
20	Correct	1 ms	1748 KB	Output is correct
21	Correct	2 ms	1620 KB	Output is correct
22	Correct	9 ms	1736 KB	Output is correct
23	Correct	5 ms	1620 KB	Output is correct
24	Correct	2 ms	1620 KB	Output is correct
25	Correct	3 ms	1620 KB	Output is correct
26	Correct	1 ms	1748 KB	Output is correct
27	Correct	1 ms	1620 KB	Output is correct
28	Correct	2 ms	1732 KB	Output is correct

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	4 ms	368 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Runtime error	1 ms	468 KB	Execution killed with signal 11
10	Halted	0 ms	0 KB	-

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1620 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	1620 KB	Output is correct
7	Correct	1 ms	1620 KB	Output is correct
8	Correct	1 ms	1620 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	1620 KB	Output is correct
16	Correct	1 ms	1620 KB	Output is correct
17	Correct	1 ms	1620 KB	Output is correct
18	Correct	1 ms	1620 KB	Output is correct
19	Correct	1 ms	1620 KB	Output is correct
20	Correct	1 ms	1620 KB	Output is correct
21	Correct	1 ms	1620 KB	Output is correct
22	Correct	1 ms	1620 KB	Output is correct
23	Correct	1 ms	1620 KB	Output is correct
24	Correct	1 ms	1620 KB	Output is correct
25	Correct	1 ms	1620 KB	Output is correct
26	Correct	1 ms	1652 KB	Output is correct
27	Correct	1 ms	1620 KB	Output is correct
28	Correct	1 ms	1620 KB	Output is correct
29	Correct	1 ms	1620 KB	Output is correct
30	Correct	1 ms	1620 KB	Output is correct
31	Correct	1 ms	1748 KB	Output is correct
32	Correct	1 ms	1620 KB	Output is correct
33	Correct	1 ms	1620 KB	Output is correct
34	Correct	1 ms	1620 KB	Output is correct
35	Correct	1 ms	1620 KB	Output is correct
36	Correct	1 ms	1620 KB	Output is correct
37	Correct	1 ms	1620 KB	Output is correct

Subtask #4
45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1620 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	1620 KB	Output is correct
6	Correct	1 ms	1620 KB	Output is correct
7	Correct	1 ms	1620 KB	Output is correct
8	Correct	4 ms	376 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	54 ms	1716 KB	Output is correct
11	Correct	1 ms	1620 KB	Output is correct
12	Correct	4 ms	1732 KB	Output is correct
13	Correct	4 ms	1748 KB	Output is correct
14	Correct	2 ms	1620 KB	Output is correct
15	Correct	3 ms	1748 KB	Output is correct
16	Correct	2 ms	1748 KB	Output is correct
17	Correct	1 ms	1620 KB	Output is correct
18	Correct	2 ms	1620 KB	Output is correct
19	Correct	1 ms	1620 KB	Output is correct
20	Correct	1 ms	1748 KB	Output is correct
21	Correct	2 ms	1620 KB	Output is correct
22	Correct	9 ms	1736 KB	Output is correct
23	Correct	5 ms	1620 KB	Output is correct
24	Correct	2 ms	1620 KB	Output is correct
25	Correct	3 ms	1620 KB	Output is correct
26	Correct	1 ms	1748 KB	Output is correct
27	Correct	1 ms	1620 KB	Output is correct
28	Correct	2 ms	1732 KB	Output is correct
29	Correct	1 ms	1620 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	0 ms	212 KB	Output is correct
32	Correct	1 ms	212 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	1620 KB	Output is correct
35	Correct	1 ms	1620 KB	Output is correct
36	Correct	1 ms	1620 KB	Output is correct
37	Correct	0 ms	212 KB	Output is correct
38	Correct	0 ms	340 KB	Output is correct
39	Correct	0 ms	212 KB	Output is correct
40	Correct	0 ms	340 KB	Output is correct
41	Correct	1 ms	212 KB	Output is correct
42	Correct	0 ms	212 KB	Output is correct
43	Correct	1 ms	1620 KB	Output is correct
44	Correct	1 ms	1620 KB	Output is correct
45	Correct	1 ms	1620 KB	Output is correct
46	Correct	1 ms	1620 KB	Output is correct
47	Correct	1 ms	1620 KB	Output is correct
48	Correct	1 ms	1620 KB	Output is correct
49	Correct	1 ms	1620 KB	Output is correct
50	Correct	1 ms	1620 KB	Output is correct
51	Correct	1 ms	1620 KB	Output is correct
52	Correct	1 ms	1620 KB	Output is correct
53	Correct	1 ms	1620 KB	Output is correct
54	Correct	1 ms	1652 KB	Output is correct
55	Correct	1 ms	1620 KB	Output is correct
56	Correct	1 ms	1620 KB	Output is correct
57	Correct	1 ms	1620 KB	Output is correct
58	Correct	1 ms	1620 KB	Output is correct
59	Correct	1 ms	1748 KB	Output is correct
60	Correct	1 ms	1620 KB	Output is correct
61	Correct	1 ms	1620 KB	Output is correct
62	Correct	1 ms	1620 KB	Output is correct
63	Correct	1 ms	1620 KB	Output is correct
64	Correct	1 ms	1620 KB	Output is correct
65	Correct	1 ms	1620 KB	Output is correct
66	Correct	1 ms	1620 KB	Output is correct
67	Correct	1 ms	340 KB	Output is correct
68	Correct	0 ms	340 KB	Output is correct
69	Correct	1 ms	332 KB	Output is correct
70	Correct	1 ms	1620 KB	Output is correct
71	Correct	4 ms	1620 KB	Output is correct
72	Correct	3 ms	1620 KB	Output is correct
73	Correct	1 ms	1620 KB	Output is correct
74	Correct	1 ms	1620 KB	Output is correct
75	Correct	4 ms	1620 KB	Output is correct
76	Correct	2 ms	1620 KB	Output is correct
77	Correct	2 ms	1620 KB	Output is correct
78	Correct	2 ms	1748 KB	Output is correct
79	Correct	2 ms	1620 KB	Output is correct
80	Correct	1 ms	1620 KB	Output is correct
81	Correct	1 ms	1620 KB	Output is correct
82	Correct	2 ms	1620 KB	Output is correct
83	Correct	1 ms	1620 KB	Output is correct
84	Correct	6 ms	1620 KB	Output is correct
85	Correct	1 ms	1620 KB	Output is correct
86	Correct	3 ms	1620 KB	Output is correct
87	Correct	3 ms	1620 KB	Output is correct
88	Correct	3 ms	1620 KB	Output is correct
89	Correct	3 ms	1732 KB	Output is correct
90	Correct	4 ms	1620 KB	Output is correct
91	Correct	3 ms	1620 KB	Output is correct
92	Correct	6 ms	1620 KB	Output is correct
93	Correct	8 ms	1748 KB	Output is correct
94	Correct	17 ms	1620 KB	Output is correct
95	Correct	3 ms	1620 KB	Output is correct
96	Correct	2 ms	1620 KB	Output is correct
97	Correct	3 ms	1748 KB	Output is correct

Subtask #5
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1620 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	1620 KB	Output is correct
6	Correct	1 ms	1620 KB	Output is correct
7	Correct	1 ms	1620 KB	Output is correct
8	Correct	4 ms	376 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	54 ms	1716 KB	Output is correct
11	Correct	1 ms	1620 KB	Output is correct
12	Correct	4 ms	1732 KB	Output is correct
13	Correct	4 ms	1748 KB	Output is correct
14	Correct	2 ms	1620 KB	Output is correct
15	Correct	3 ms	1748 KB	Output is correct
16	Correct	2 ms	1748 KB	Output is correct
17	Correct	1 ms	1620 KB	Output is correct
18	Correct	2 ms	1620 KB	Output is correct
19	Correct	1 ms	1620 KB	Output is correct
20	Correct	1 ms	1748 KB	Output is correct
21	Correct	2 ms	1620 KB	Output is correct
22	Correct	9 ms	1736 KB	Output is correct
23	Correct	5 ms	1620 KB	Output is correct
24	Correct	2 ms	1620 KB	Output is correct
25	Correct	3 ms	1620 KB	Output is correct
26	Correct	1 ms	1748 KB	Output is correct
27	Correct	1 ms	1620 KB	Output is correct
28	Correct	2 ms	1732 KB	Output is correct
29	Correct	1 ms	1620 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	0 ms	212 KB	Output is correct
32	Correct	1 ms	212 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	1620 KB	Output is correct
35	Correct	1 ms	1620 KB	Output is correct
36	Correct	1 ms	1620 KB	Output is correct
37	Correct	0 ms	212 KB	Output is correct
38	Correct	0 ms	340 KB	Output is correct
39	Correct	0 ms	212 KB	Output is correct
40	Correct	0 ms	340 KB	Output is correct
41	Correct	1 ms	212 KB	Output is correct
42	Correct	0 ms	212 KB	Output is correct
43	Correct	1 ms	1620 KB	Output is correct
44	Correct	1 ms	1620 KB	Output is correct
45	Correct	1 ms	1620 KB	Output is correct
46	Correct	1 ms	1620 KB	Output is correct
47	Correct	1 ms	1620 KB	Output is correct
48	Correct	1 ms	1620 KB	Output is correct
49	Correct	1 ms	1620 KB	Output is correct
50	Correct	1 ms	1620 KB	Output is correct
51	Correct	1 ms	1620 KB	Output is correct
52	Correct	1 ms	1620 KB	Output is correct
53	Correct	1 ms	1620 KB	Output is correct
54	Correct	1 ms	1652 KB	Output is correct
55	Correct	1 ms	1620 KB	Output is correct
56	Correct	1 ms	1620 KB	Output is correct
57	Correct	1 ms	1620 KB	Output is correct
58	Correct	1 ms	1620 KB	Output is correct
59	Correct	1 ms	1748 KB	Output is correct
60	Correct	1 ms	1620 KB	Output is correct
61	Correct	1 ms	1620 KB	Output is correct
62	Correct	1 ms	1620 KB	Output is correct
63	Correct	1 ms	1620 KB	Output is correct
64	Correct	1 ms	1620 KB	Output is correct
65	Correct	1 ms	1620 KB	Output is correct
66	Correct	1 ms	1620 KB	Output is correct
67	Correct	1 ms	340 KB	Output is correct
68	Correct	0 ms	340 KB	Output is correct
69	Correct	1 ms	332 KB	Output is correct
70	Correct	1 ms	1620 KB	Output is correct
71	Correct	4 ms	1620 KB	Output is correct
72	Correct	3 ms	1620 KB	Output is correct
73	Correct	1 ms	1620 KB	Output is correct
74	Correct	1 ms	1620 KB	Output is correct
75	Correct	4 ms	1620 KB	Output is correct
76	Correct	2 ms	1620 KB	Output is correct
77	Correct	2 ms	1620 KB	Output is correct
78	Correct	2 ms	1748 KB	Output is correct
79	Correct	2 ms	1620 KB	Output is correct
80	Correct	1 ms	1620 KB	Output is correct
81	Correct	1 ms	1620 KB	Output is correct
82	Correct	2 ms	1620 KB	Output is correct
83	Correct	1 ms	1620 KB	Output is correct
84	Correct	6 ms	1620 KB	Output is correct
85	Correct	1 ms	1620 KB	Output is correct
86	Correct	3 ms	1620 KB	Output is correct
87	Correct	3 ms	1620 KB	Output is correct
88	Correct	3 ms	1620 KB	Output is correct
89	Correct	3 ms	1732 KB	Output is correct
90	Correct	4 ms	1620 KB	Output is correct
91	Correct	3 ms	1620 KB	Output is correct
92	Correct	6 ms	1620 KB	Output is correct
93	Correct	8 ms	1748 KB	Output is correct
94	Correct	17 ms	1620 KB	Output is correct
95	Correct	3 ms	1620 KB	Output is correct
96	Correct	2 ms	1620 KB	Output is correct
97	Correct	3 ms	1748 KB	Output is correct
98	Runtime error	1 ms	468 KB	Execution killed with signal 11
99	Halted	0 ms	0 KB	-

Subtask #6
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1620 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	1620 KB	Output is correct
6	Correct	1 ms	1620 KB	Output is correct
7	Correct	1 ms	1620 KB	Output is correct
8	Correct	4 ms	376 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	54 ms	1716 KB	Output is correct
11	Correct	1 ms	1620 KB	Output is correct
12	Correct	4 ms	1732 KB	Output is correct
13	Correct	4 ms	1748 KB	Output is correct
14	Correct	2 ms	1620 KB	Output is correct
15	Correct	3 ms	1748 KB	Output is correct
16	Correct	2 ms	1748 KB	Output is correct
17	Correct	1 ms	1620 KB	Output is correct
18	Correct	2 ms	1620 KB	Output is correct
19	Correct	1 ms	1620 KB	Output is correct
20	Correct	1 ms	1748 KB	Output is correct
21	Correct	2 ms	1620 KB	Output is correct
22	Correct	9 ms	1736 KB	Output is correct
23	Correct	5 ms	1620 KB	Output is correct
24	Correct	2 ms	1620 KB	Output is correct
25	Correct	3 ms	1620 KB	Output is correct
26	Correct	1 ms	1748 KB	Output is correct
27	Correct	1 ms	1620 KB	Output is correct
28	Correct	2 ms	1732 KB	Output is correct
29	Correct	0 ms	340 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Correct	0 ms	212 KB	Output is correct
32	Correct	0 ms	340 KB	Output is correct
33	Correct	4 ms	368 KB	Output is correct
34	Correct	0 ms	340 KB	Output is correct
35	Correct	1 ms	212 KB	Output is correct
36	Correct	1 ms	340 KB	Output is correct
37	Runtime error	1 ms	468 KB	Execution killed with signal 11
38	Halted	0 ms	0 KB	-

Submission #789309

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 0 / 7.0

Subtask #3 12.0 / 12.0

Subtask #4 45.0 / 45.0

Subtask #5 0 / 15.0

Subtask #6 0 / 15.0

Subtask #1
6.0 / 6.0

Subtask #2
0 / 7.0

Subtask #3
12.0 / 12.0

Subtask #4
45.0 / 45.0

Subtask #5
0 / 15.0

Subtask #6
0 / 15.0