Submission #574294

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
574294	2022-06-08T09:46:40 Z	8e7	Uplifting Excursion (BOI22_vault)	C++17	30 / 100	3286 ms	48084 KB

vault

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 3000005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
int dp[2][maxn];
int main() {
	io
		int m;
	ll L;
	cin >> m >> L;
	vector<ll> a(2*m+1), ex(2*m+1);	
	ll mins = 0, ans = 0;
	for (int i = 0;i < 2*m+1;i++) {
		cin >> a[i];
		if (i == m) ans += a[i], a[i] = 0;
	}
	for (int i = m+1;i < 2*m+1;i++) {
		ll p = min(a[i], L / (i-m));
		ans += p;
		L -= p * (i-m);
		a[i] -= p;

		ex[i] = min(a[i], (ll)m);
		ex[2 * m - i] = min(p,(ll)m);
	}
	for (int i = 0;i < 2 * m+1;i++) {
		if (i < m) mins += ex[i] * (i - m);
	}
	for (int i = 0;i < maxn;i++) dp[0][i] = dp[1][i] = -inf;	

	dp[0][-mins] = 0;
	dp[1][-mins] = 0;
	for (int i = 0;i < 2*m+1;i++) {
		ll cnt = 1;
		vector<int> num;
		while (ex[i] >= cnt) {
			num.push_back(cnt);
			ex[i] -= cnt;
			cnt <<= 1;
		}
		if (ex[i] > 0) num.push_back(ex[i]);
		for (int p:num) {
			for (int j = 0;j < maxn;j++) {
				int val = j + p * (i-m);
				int del = i < m ? -p : p;
				if (val >= 0 && val < maxn) dp[1][val] = max(dp[1][val], dp[0][j] + del);
			}
			for (int j = 0;j < maxn;j++) dp[0][j] = dp[1][j];
		}
	}
	if (L - mins >= maxn || L - mins < 0 || dp[0][L - mins] < -maxn) cout << "impossible\n";
	else cout << dp[0][L - mins]+ans << "\n";
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	35 ms	23764 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	35 ms	23764 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3-1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	23784 KB	Output is correct
2	Correct	643 ms	23784 KB	Output is correct
3	Correct	192 ms	23792 KB	Output is correct
4	Correct	686 ms	23780 KB	Output is correct
5	Correct	733 ms	23792 KB	Output is correct
6	Correct	637 ms	23884 KB	Output is correct
7	Correct	82 ms	23792 KB	Output is correct
8	Correct	94 ms	23764 KB	Output is correct
9	Correct	361 ms	23764 KB	Output is correct
10	Correct	481 ms	23784 KB	Output is correct

Subtask #3-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	23784 KB	Output is correct
2	Correct	643 ms	23784 KB	Output is correct
3	Correct	192 ms	23792 KB	Output is correct
4	Correct	686 ms	23780 KB	Output is correct
5	Correct	733 ms	23792 KB	Output is correct
6	Correct	637 ms	23884 KB	Output is correct
7	Correct	82 ms	23792 KB	Output is correct
8	Correct	94 ms	23764 KB	Output is correct
9	Correct	361 ms	23764 KB	Output is correct
10	Correct	481 ms	23784 KB	Output is correct
11	Incorrect	34 ms	23764 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #4-1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	23784 KB	Output is correct
2	Correct	643 ms	23784 KB	Output is correct
3	Correct	192 ms	23792 KB	Output is correct
4	Correct	686 ms	23780 KB	Output is correct
5	Correct	733 ms	23792 KB	Output is correct
6	Correct	637 ms	23884 KB	Output is correct
7	Correct	82 ms	23792 KB	Output is correct
8	Correct	94 ms	23764 KB	Output is correct
9	Correct	361 ms	23764 KB	Output is correct
10	Correct	481 ms	23784 KB	Output is correct
11	Correct	150 ms	23780 KB	Output is correct
12	Correct	647 ms	23788 KB	Output is correct
13	Correct	198 ms	23780 KB	Output is correct
14	Correct	688 ms	23780 KB	Output is correct
15	Correct	719 ms	23788 KB	Output is correct
16	Correct	646 ms	23892 KB	Output is correct
17	Correct	80 ms	23764 KB	Output is correct
18	Correct	96 ms	23684 KB	Output is correct
19	Correct	350 ms	23788 KB	Output is correct
20	Correct	476 ms	23780 KB	Output is correct
21	Correct	76 ms	23764 KB	Output is correct
22	Correct	112 ms	23784 KB	Output is correct
23	Correct	1249 ms	23784 KB	Output is correct
24	Correct	560 ms	23796 KB	Output is correct
25	Correct	1198 ms	23780 KB	Output is correct
26	Correct	1417 ms	23780 KB	Output is correct
27	Correct	1291 ms	23784 KB	Output is correct
28	Correct	999 ms	23788 KB	Output is correct

Subtask #4-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	35 ms	23764 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5-1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	23784 KB	Output is correct
2	Correct	643 ms	23784 KB	Output is correct
3	Correct	192 ms	23792 KB	Output is correct
4	Correct	686 ms	23780 KB	Output is correct
5	Correct	733 ms	23792 KB	Output is correct
6	Correct	637 ms	23884 KB	Output is correct
7	Correct	82 ms	23792 KB	Output is correct
8	Correct	94 ms	23764 KB	Output is correct
9	Correct	361 ms	23764 KB	Output is correct
10	Correct	481 ms	23784 KB	Output is correct
11	Correct	150 ms	23780 KB	Output is correct
12	Correct	647 ms	23788 KB	Output is correct
13	Correct	198 ms	23780 KB	Output is correct
14	Correct	688 ms	23780 KB	Output is correct
15	Correct	719 ms	23788 KB	Output is correct
16	Correct	646 ms	23892 KB	Output is correct
17	Correct	80 ms	23764 KB	Output is correct
18	Correct	96 ms	23684 KB	Output is correct
19	Correct	350 ms	23788 KB	Output is correct
20	Correct	476 ms	23780 KB	Output is correct
21	Correct	76 ms	23764 KB	Output is correct
22	Correct	112 ms	23784 KB	Output is correct
23	Correct	1249 ms	23784 KB	Output is correct
24	Correct	560 ms	23796 KB	Output is correct
25	Correct	1198 ms	23780 KB	Output is correct
26	Correct	1417 ms	23780 KB	Output is correct
27	Correct	1291 ms	23784 KB	Output is correct
28	Correct	999 ms	23788 KB	Output is correct
29	Correct	141 ms	23764 KB	Output is correct
30	Correct	687 ms	23780 KB	Output is correct
31	Correct	191 ms	23792 KB	Output is correct
32	Correct	682 ms	23784 KB	Output is correct
33	Correct	731 ms	23884 KB	Output is correct
34	Correct	634 ms	23784 KB	Output is correct
35	Correct	83 ms	23788 KB	Output is correct
36	Correct	99 ms	23764 KB	Output is correct
37	Correct	344 ms	23784 KB	Output is correct
38	Correct	459 ms	23784 KB	Output is correct
39	Correct	77 ms	23780 KB	Output is correct
40	Correct	115 ms	23784 KB	Output is correct
41	Correct	1288 ms	23784 KB	Output is correct
42	Correct	559 ms	23788 KB	Output is correct
43	Correct	1206 ms	23784 KB	Output is correct
44	Correct	1444 ms	23784 KB	Output is correct
45	Correct	1289 ms	23784 KB	Output is correct
46	Correct	949 ms	23788 KB	Output is correct
47	Correct	88 ms	23792 KB	Output is correct
48	Correct	121 ms	23788 KB	Output is correct
49	Correct	2811 ms	23788 KB	Output is correct
50	Correct	1206 ms	23784 KB	Output is correct
51	Correct	2940 ms	23788 KB	Output is correct
52	Correct	3273 ms	23792 KB	Output is correct
53	Correct	2794 ms	23788 KB	Output is correct
54	Correct	2353 ms	23788 KB	Output is correct

Subtask #5-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	35 ms	23764 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	23784 KB	Output is correct
2	Correct	643 ms	23784 KB	Output is correct
3	Correct	192 ms	23792 KB	Output is correct
4	Correct	686 ms	23780 KB	Output is correct
5	Correct	733 ms	23792 KB	Output is correct
6	Correct	637 ms	23884 KB	Output is correct
7	Correct	82 ms	23792 KB	Output is correct
8	Correct	94 ms	23764 KB	Output is correct
9	Correct	361 ms	23764 KB	Output is correct
10	Correct	481 ms	23784 KB	Output is correct
11	Correct	150 ms	23780 KB	Output is correct
12	Correct	647 ms	23788 KB	Output is correct
13	Correct	198 ms	23780 KB	Output is correct
14	Correct	688 ms	23780 KB	Output is correct
15	Correct	719 ms	23788 KB	Output is correct
16	Correct	646 ms	23892 KB	Output is correct
17	Correct	80 ms	23764 KB	Output is correct
18	Correct	96 ms	23684 KB	Output is correct
19	Correct	350 ms	23788 KB	Output is correct
20	Correct	476 ms	23780 KB	Output is correct
21	Correct	76 ms	23764 KB	Output is correct
22	Correct	112 ms	23784 KB	Output is correct
23	Correct	1249 ms	23784 KB	Output is correct
24	Correct	560 ms	23796 KB	Output is correct
25	Correct	1198 ms	23780 KB	Output is correct
26	Correct	1417 ms	23780 KB	Output is correct
27	Correct	1291 ms	23784 KB	Output is correct
28	Correct	999 ms	23788 KB	Output is correct
29	Correct	141 ms	23764 KB	Output is correct
30	Correct	687 ms	23780 KB	Output is correct
31	Correct	191 ms	23792 KB	Output is correct
32	Correct	682 ms	23784 KB	Output is correct
33	Correct	731 ms	23884 KB	Output is correct
34	Correct	634 ms	23784 KB	Output is correct
35	Correct	83 ms	23788 KB	Output is correct
36	Correct	99 ms	23764 KB	Output is correct
37	Correct	344 ms	23784 KB	Output is correct
38	Correct	459 ms	23784 KB	Output is correct
39	Correct	77 ms	23780 KB	Output is correct
40	Correct	115 ms	23784 KB	Output is correct
41	Correct	1288 ms	23784 KB	Output is correct
42	Correct	559 ms	23788 KB	Output is correct
43	Correct	1206 ms	23784 KB	Output is correct
44	Correct	1444 ms	23784 KB	Output is correct
45	Correct	1289 ms	23784 KB	Output is correct
46	Correct	949 ms	23788 KB	Output is correct
47	Correct	88 ms	23792 KB	Output is correct
48	Correct	121 ms	23788 KB	Output is correct
49	Correct	2811 ms	23788 KB	Output is correct
50	Correct	1206 ms	23784 KB	Output is correct
51	Correct	2940 ms	23788 KB	Output is correct
52	Correct	3273 ms	23792 KB	Output is correct
53	Correct	2794 ms	23788 KB	Output is correct
54	Correct	2353 ms	23788 KB	Output is correct
55	Correct	144 ms	23796 KB	Output is correct
56	Correct	667 ms	23780 KB	Output is correct
57	Correct	198 ms	23752 KB	Output is correct
58	Correct	692 ms	23780 KB	Output is correct
59	Correct	745 ms	23788 KB	Output is correct
60	Correct	643 ms	23796 KB	Output is correct
61	Correct	83 ms	23784 KB	Output is correct
62	Correct	95 ms	23784 KB	Output is correct
63	Correct	365 ms	23780 KB	Output is correct
64	Correct	473 ms	23764 KB	Output is correct
65	Correct	81 ms	23784 KB	Output is correct
66	Correct	109 ms	23788 KB	Output is correct
67	Correct	1260 ms	23788 KB	Output is correct
68	Correct	548 ms	23884 KB	Output is correct
69	Correct	1192 ms	23780 KB	Output is correct
70	Correct	1424 ms	23780 KB	Output is correct
71	Correct	1291 ms	23796 KB	Output is correct
72	Correct	955 ms	23780 KB	Output is correct
73	Correct	86 ms	23764 KB	Output is correct
74	Correct	131 ms	23764 KB	Output is correct
75	Correct	2781 ms	23792 KB	Output is correct
76	Correct	1224 ms	23788 KB	Output is correct
77	Correct	2959 ms	23784 KB	Output is correct
78	Correct	3286 ms	23788 KB	Output is correct
79	Correct	2850 ms	23792 KB	Output is correct
80	Correct	2374 ms	23788 KB	Output is correct
81	Runtime error	35 ms	48084 KB	Execution killed with signal 11
82	Halted	0 ms	0 KB	-

Subtask #6-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	35 ms	23764 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Submission #574294

Compilation message