Submission #574310

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
574310	2022-06-08T10:10:13 Z	8e7	Uplifting Excursion (BOI22_vault)	C++17	20 / 100	5000 ms	53536 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 13600005
    #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	130 ms	53484 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	130 ms	53484 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	537 ms	53524 KB	Output is correct
2	Correct	2252 ms	53528 KB	Output is correct
3	Correct	659 ms	53520 KB	Output is correct
4	Correct	2531 ms	53528 KB	Output is correct
5	Correct	2744 ms	53524 KB	Output is correct
6	Correct	2208 ms	53524 KB	Output is correct
7	Correct	290 ms	53528 KB	Output is correct
8	Correct	320 ms	53524 KB	Output is correct
9	Correct	1190 ms	53528 KB	Output is correct
10	Correct	1601 ms	53520 KB	Output is correct

Subtask #3-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	537 ms	53524 KB	Output is correct
2	Correct	2252 ms	53528 KB	Output is correct
3	Correct	659 ms	53520 KB	Output is correct
4	Correct	2531 ms	53528 KB	Output is correct
5	Correct	2744 ms	53524 KB	Output is correct
6	Correct	2208 ms	53524 KB	Output is correct
7	Correct	290 ms	53528 KB	Output is correct
8	Correct	320 ms	53524 KB	Output is correct
9	Correct	1190 ms	53528 KB	Output is correct
10	Correct	1601 ms	53520 KB	Output is correct
11	Incorrect	130 ms	53520 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	537 ms	53524 KB	Output is correct
2	Correct	2252 ms	53528 KB	Output is correct
3	Correct	659 ms	53520 KB	Output is correct
4	Correct	2531 ms	53528 KB	Output is correct
5	Correct	2744 ms	53524 KB	Output is correct
6	Correct	2208 ms	53524 KB	Output is correct
7	Correct	290 ms	53528 KB	Output is correct
8	Correct	320 ms	53524 KB	Output is correct
9	Correct	1190 ms	53528 KB	Output is correct
10	Correct	1601 ms	53520 KB	Output is correct
11	Correct	498 ms	53524 KB	Output is correct
12	Correct	2096 ms	53524 KB	Output is correct
13	Correct	647 ms	53520 KB	Output is correct
14	Correct	2322 ms	53528 KB	Output is correct
15	Correct	2417 ms	53524 KB	Output is correct
16	Correct	2079 ms	53528 KB	Output is correct
17	Correct	274 ms	53524 KB	Output is correct
18	Correct	332 ms	53532 KB	Output is correct
19	Correct	1236 ms	53520 KB	Output is correct
20	Correct	1600 ms	53532 KB	Output is correct
21	Correct	247 ms	53520 KB	Output is correct
22	Correct	392 ms	53520 KB	Output is correct
23	Correct	4830 ms	53528 KB	Output is correct
24	Correct	1857 ms	53520 KB	Output is correct
25	Correct	4191 ms	53528 KB	Output is correct
26	Correct	4706 ms	53528 KB	Output is correct
27	Correct	4442 ms	53524 KB	Output is correct
28	Correct	3077 ms	53528 KB	Output is correct

Subtask #4-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	130 ms	53484 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	537 ms	53524 KB	Output is correct
2	Correct	2252 ms	53528 KB	Output is correct
3	Correct	659 ms	53520 KB	Output is correct
4	Correct	2531 ms	53528 KB	Output is correct
5	Correct	2744 ms	53524 KB	Output is correct
6	Correct	2208 ms	53524 KB	Output is correct
7	Correct	290 ms	53528 KB	Output is correct
8	Correct	320 ms	53524 KB	Output is correct
9	Correct	1190 ms	53528 KB	Output is correct
10	Correct	1601 ms	53520 KB	Output is correct
11	Correct	498 ms	53524 KB	Output is correct
12	Correct	2096 ms	53524 KB	Output is correct
13	Correct	647 ms	53520 KB	Output is correct
14	Correct	2322 ms	53528 KB	Output is correct
15	Correct	2417 ms	53524 KB	Output is correct
16	Correct	2079 ms	53528 KB	Output is correct
17	Correct	274 ms	53524 KB	Output is correct
18	Correct	332 ms	53532 KB	Output is correct
19	Correct	1236 ms	53520 KB	Output is correct
20	Correct	1600 ms	53532 KB	Output is correct
21	Correct	247 ms	53520 KB	Output is correct
22	Correct	392 ms	53520 KB	Output is correct
23	Correct	4830 ms	53528 KB	Output is correct
24	Correct	1857 ms	53520 KB	Output is correct
25	Correct	4191 ms	53528 KB	Output is correct
26	Correct	4706 ms	53528 KB	Output is correct
27	Correct	4442 ms	53524 KB	Output is correct
28	Correct	3077 ms	53528 KB	Output is correct
29	Correct	456 ms	53520 KB	Output is correct
30	Correct	2210 ms	53524 KB	Output is correct
31	Correct	597 ms	53520 KB	Output is correct
32	Correct	2308 ms	53524 KB	Output is correct
33	Correct	2503 ms	53524 KB	Output is correct
34	Correct	2024 ms	53524 KB	Output is correct
35	Correct	260 ms	53520 KB	Output is correct
36	Correct	307 ms	53524 KB	Output is correct
37	Correct	1347 ms	53524 KB	Output is correct
38	Correct	1625 ms	53524 KB	Output is correct
39	Correct	294 ms	53520 KB	Output is correct
40	Correct	355 ms	53520 KB	Output is correct
41	Correct	4725 ms	53524 KB	Output is correct
42	Correct	1933 ms	53528 KB	Output is correct
43	Correct	3647 ms	53528 KB	Output is correct
44	Correct	4798 ms	53520 KB	Output is correct
45	Correct	4154 ms	53524 KB	Output is correct
46	Correct	3390 ms	53536 KB	Output is correct
47	Correct	262 ms	53524 KB	Output is correct
48	Correct	444 ms	53528 KB	Output is correct
49	Execution timed out	5059 ms	53508 KB	Time limit exceeded
50	Halted	0 ms	0 KB	-

Subtask #5-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	130 ms	53484 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	537 ms	53524 KB	Output is correct
2	Correct	2252 ms	53528 KB	Output is correct
3	Correct	659 ms	53520 KB	Output is correct
4	Correct	2531 ms	53528 KB	Output is correct
5	Correct	2744 ms	53524 KB	Output is correct
6	Correct	2208 ms	53524 KB	Output is correct
7	Correct	290 ms	53528 KB	Output is correct
8	Correct	320 ms	53524 KB	Output is correct
9	Correct	1190 ms	53528 KB	Output is correct
10	Correct	1601 ms	53520 KB	Output is correct
11	Correct	498 ms	53524 KB	Output is correct
12	Correct	2096 ms	53524 KB	Output is correct
13	Correct	647 ms	53520 KB	Output is correct
14	Correct	2322 ms	53528 KB	Output is correct
15	Correct	2417 ms	53524 KB	Output is correct
16	Correct	2079 ms	53528 KB	Output is correct
17	Correct	274 ms	53524 KB	Output is correct
18	Correct	332 ms	53532 KB	Output is correct
19	Correct	1236 ms	53520 KB	Output is correct
20	Correct	1600 ms	53532 KB	Output is correct
21	Correct	247 ms	53520 KB	Output is correct
22	Correct	392 ms	53520 KB	Output is correct
23	Correct	4830 ms	53528 KB	Output is correct
24	Correct	1857 ms	53520 KB	Output is correct
25	Correct	4191 ms	53528 KB	Output is correct
26	Correct	4706 ms	53528 KB	Output is correct
27	Correct	4442 ms	53524 KB	Output is correct
28	Correct	3077 ms	53528 KB	Output is correct
29	Correct	456 ms	53520 KB	Output is correct
30	Correct	2210 ms	53524 KB	Output is correct
31	Correct	597 ms	53520 KB	Output is correct
32	Correct	2308 ms	53524 KB	Output is correct
33	Correct	2503 ms	53524 KB	Output is correct
34	Correct	2024 ms	53524 KB	Output is correct
35	Correct	260 ms	53520 KB	Output is correct
36	Correct	307 ms	53524 KB	Output is correct
37	Correct	1347 ms	53524 KB	Output is correct
38	Correct	1625 ms	53524 KB	Output is correct
39	Correct	294 ms	53520 KB	Output is correct
40	Correct	355 ms	53520 KB	Output is correct
41	Correct	4725 ms	53524 KB	Output is correct
42	Correct	1933 ms	53528 KB	Output is correct
43	Correct	3647 ms	53528 KB	Output is correct
44	Correct	4798 ms	53520 KB	Output is correct
45	Correct	4154 ms	53524 KB	Output is correct
46	Correct	3390 ms	53536 KB	Output is correct
47	Correct	262 ms	53524 KB	Output is correct
48	Correct	444 ms	53528 KB	Output is correct
49	Execution timed out	5059 ms	53508 KB	Time limit exceeded
50	Halted	0 ms	0 KB	-

Subtask #6-2
0 / 10.0

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

Submission #574310

Compilation message