Submission #574309

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
574309	2022-06-08T10:09:56 Z	8e7	Uplifting Excursion (BOI22_vault)	C++17	20 / 100	5000 ms	47276 KB

vault

    //Challenge: Accepted
    #include <bits/stdc++.h>
    #pragma GCC optimize("Ofast")
    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 12000005
    #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[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[i] = -inf;	
     
    	dp[-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) {
    			if (i - m > 0) {
    				for (int j = maxn - 1;j >= 0;j--) {
    					int val = j + p * (i-m);
    					if (val >= maxn) continue;
    					int del = i < m ? -p : p;
    					dp[val] = max(dp[val], dp[j] + del);
    				}
    			} else {
    				for (int j = 0;j < maxn;j++) {
    					int val = j + p * (i-m);
    					if (val < 0) continue;
    					int del = i < m ? -p : p;
    					dp[val] = max(dp[val], dp[j] + del);
    				}
    			}
    		}
    	}
    	if (L - mins >= maxn || L - mins < 0 || dp[L - mins] < -maxn) cout << "impossible\n";
    	else cout << dp[L - mins]+ans << "\n";
    }

Subtask #1
0 / 5.0

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

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	125 ms	47188 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	593 ms	47268 KB	Output is correct
2	Correct	1986 ms	47260 KB	Output is correct
3	Correct	598 ms	47264 KB	Output is correct
4	Correct	2237 ms	47260 KB	Output is correct
5	Correct	2077 ms	47264 KB	Output is correct
6	Correct	1809 ms	47260 KB	Output is correct
7	Correct	235 ms	47268 KB	Output is correct
8	Correct	280 ms	47200 KB	Output is correct
9	Correct	1033 ms	47264 KB	Output is correct
10	Correct	1363 ms	47264 KB	Output is correct

Subtask #3-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	593 ms	47268 KB	Output is correct
2	Correct	1986 ms	47260 KB	Output is correct
3	Correct	598 ms	47264 KB	Output is correct
4	Correct	2237 ms	47260 KB	Output is correct
5	Correct	2077 ms	47264 KB	Output is correct
6	Correct	1809 ms	47260 KB	Output is correct
7	Correct	235 ms	47268 KB	Output is correct
8	Correct	280 ms	47200 KB	Output is correct
9	Correct	1033 ms	47264 KB	Output is correct
10	Correct	1363 ms	47264 KB	Output is correct
11	Incorrect	114 ms	47264 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	593 ms	47268 KB	Output is correct
2	Correct	1986 ms	47260 KB	Output is correct
3	Correct	598 ms	47264 KB	Output is correct
4	Correct	2237 ms	47260 KB	Output is correct
5	Correct	2077 ms	47264 KB	Output is correct
6	Correct	1809 ms	47260 KB	Output is correct
7	Correct	235 ms	47268 KB	Output is correct
8	Correct	280 ms	47200 KB	Output is correct
9	Correct	1033 ms	47264 KB	Output is correct
10	Correct	1363 ms	47264 KB	Output is correct
11	Correct	420 ms	47264 KB	Output is correct
12	Correct	2035 ms	47264 KB	Output is correct
13	Correct	551 ms	47276 KB	Output is correct
14	Correct	2194 ms	47264 KB	Output is correct
15	Correct	2285 ms	47268 KB	Output is correct
16	Correct	2254 ms	47272 KB	Output is correct
17	Correct	247 ms	47268 KB	Output is correct
18	Correct	304 ms	47260 KB	Output is correct
19	Correct	1006 ms	47260 KB	Output is correct
20	Correct	1412 ms	47260 KB	Output is correct
21	Correct	247 ms	47264 KB	Output is correct
22	Correct	314 ms	47260 KB	Output is correct
23	Correct	3559 ms	47260 KB	Output is correct
24	Correct	1655 ms	47260 KB	Output is correct
25	Correct	3684 ms	47264 KB	Output is correct
26	Correct	4573 ms	47268 KB	Output is correct
27	Correct	3994 ms	47268 KB	Output is correct
28	Correct	2882 ms	47264 KB	Output is correct

Subtask #4-2
0 / 10.0

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

Subtask #5-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	593 ms	47268 KB	Output is correct
2	Correct	1986 ms	47260 KB	Output is correct
3	Correct	598 ms	47264 KB	Output is correct
4	Correct	2237 ms	47260 KB	Output is correct
5	Correct	2077 ms	47264 KB	Output is correct
6	Correct	1809 ms	47260 KB	Output is correct
7	Correct	235 ms	47268 KB	Output is correct
8	Correct	280 ms	47200 KB	Output is correct
9	Correct	1033 ms	47264 KB	Output is correct
10	Correct	1363 ms	47264 KB	Output is correct
11	Correct	420 ms	47264 KB	Output is correct
12	Correct	2035 ms	47264 KB	Output is correct
13	Correct	551 ms	47276 KB	Output is correct
14	Correct	2194 ms	47264 KB	Output is correct
15	Correct	2285 ms	47268 KB	Output is correct
16	Correct	2254 ms	47272 KB	Output is correct
17	Correct	247 ms	47268 KB	Output is correct
18	Correct	304 ms	47260 KB	Output is correct
19	Correct	1006 ms	47260 KB	Output is correct
20	Correct	1412 ms	47260 KB	Output is correct
21	Correct	247 ms	47264 KB	Output is correct
22	Correct	314 ms	47260 KB	Output is correct
23	Correct	3559 ms	47260 KB	Output is correct
24	Correct	1655 ms	47260 KB	Output is correct
25	Correct	3684 ms	47264 KB	Output is correct
26	Correct	4573 ms	47268 KB	Output is correct
27	Correct	3994 ms	47268 KB	Output is correct
28	Correct	2882 ms	47264 KB	Output is correct
29	Correct	416 ms	47260 KB	Output is correct
30	Correct	2243 ms	47260 KB	Output is correct
31	Correct	585 ms	47264 KB	Output is correct
32	Correct	2043 ms	47264 KB	Output is correct
33	Correct	2345 ms	47260 KB	Output is correct
34	Correct	1902 ms	47268 KB	Output is correct
35	Correct	222 ms	47264 KB	Output is correct
36	Correct	294 ms	47260 KB	Output is correct
37	Correct	991 ms	47264 KB	Output is correct
38	Correct	1558 ms	47188 KB	Output is correct
39	Correct	236 ms	47264 KB	Output is correct
40	Correct	356 ms	47260 KB	Output is correct
41	Correct	3488 ms	47268 KB	Output is correct
42	Correct	1626 ms	47260 KB	Output is correct
43	Correct	3283 ms	47272 KB	Output is correct
44	Correct	4310 ms	47268 KB	Output is correct
45	Correct	3985 ms	47268 KB	Output is correct
46	Correct	2838 ms	47264 KB	Output is correct
47	Correct	269 ms	47268 KB	Output is correct
48	Correct	436 ms	47276 KB	Output is correct
49	Execution timed out	5070 ms	47164 KB	Time limit exceeded
50	Halted	0 ms	0 KB	-

Subtask #5-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	125 ms	47188 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	593 ms	47268 KB	Output is correct
2	Correct	1986 ms	47260 KB	Output is correct
3	Correct	598 ms	47264 KB	Output is correct
4	Correct	2237 ms	47260 KB	Output is correct
5	Correct	2077 ms	47264 KB	Output is correct
6	Correct	1809 ms	47260 KB	Output is correct
7	Correct	235 ms	47268 KB	Output is correct
8	Correct	280 ms	47200 KB	Output is correct
9	Correct	1033 ms	47264 KB	Output is correct
10	Correct	1363 ms	47264 KB	Output is correct
11	Correct	420 ms	47264 KB	Output is correct
12	Correct	2035 ms	47264 KB	Output is correct
13	Correct	551 ms	47276 KB	Output is correct
14	Correct	2194 ms	47264 KB	Output is correct
15	Correct	2285 ms	47268 KB	Output is correct
16	Correct	2254 ms	47272 KB	Output is correct
17	Correct	247 ms	47268 KB	Output is correct
18	Correct	304 ms	47260 KB	Output is correct
19	Correct	1006 ms	47260 KB	Output is correct
20	Correct	1412 ms	47260 KB	Output is correct
21	Correct	247 ms	47264 KB	Output is correct
22	Correct	314 ms	47260 KB	Output is correct
23	Correct	3559 ms	47260 KB	Output is correct
24	Correct	1655 ms	47260 KB	Output is correct
25	Correct	3684 ms	47264 KB	Output is correct
26	Correct	4573 ms	47268 KB	Output is correct
27	Correct	3994 ms	47268 KB	Output is correct
28	Correct	2882 ms	47264 KB	Output is correct
29	Correct	416 ms	47260 KB	Output is correct
30	Correct	2243 ms	47260 KB	Output is correct
31	Correct	585 ms	47264 KB	Output is correct
32	Correct	2043 ms	47264 KB	Output is correct
33	Correct	2345 ms	47260 KB	Output is correct
34	Correct	1902 ms	47268 KB	Output is correct
35	Correct	222 ms	47264 KB	Output is correct
36	Correct	294 ms	47260 KB	Output is correct
37	Correct	991 ms	47264 KB	Output is correct
38	Correct	1558 ms	47188 KB	Output is correct
39	Correct	236 ms	47264 KB	Output is correct
40	Correct	356 ms	47260 KB	Output is correct
41	Correct	3488 ms	47268 KB	Output is correct
42	Correct	1626 ms	47260 KB	Output is correct
43	Correct	3283 ms	47272 KB	Output is correct
44	Correct	4310 ms	47268 KB	Output is correct
45	Correct	3985 ms	47268 KB	Output is correct
46	Correct	2838 ms	47264 KB	Output is correct
47	Correct	269 ms	47268 KB	Output is correct
48	Correct	436 ms	47276 KB	Output is correct
49	Execution timed out	5070 ms	47164 KB	Time limit exceeded
50	Halted	0 ms	0 KB	-

Subtask #6-2
0 / 10.0

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

Submission #574309

Compilation message