Submission #792072

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
792072	2023-07-24T14:46:07 Z	ToniB	Uplifting Excursion (BOI22_vault)	C++17	5 / 100	5000 ms	369612 KB

vault

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const int K = MAXN * MAXN / 4;

int m, a[MAXN];
int dp[MAXN][MAXN * MAXN / 2];
long long L;
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> m >> L;
	for(int i = 0; i < 2 * m + 1; ++i) cin >> a[i];
	for(int i = 0; i < 2 * m + 1; ++i){
		// dp[i][j] = max{dp[i - 1][j - x * (i - m)] + x}
		for(int j = 0; j < MAXN * MAXN / 2; ++j){
			dp[i][j] = -1e9;
			for(int x = 0; x <= a[i]; ++x){
				if(j - x * (i - m) >= 0 && j - x * (i - m) < MAXN * MAXN / 2){
					if(i) dp[i][j] = max(dp[i][j], dp[i - 1][j - x * (i - m)] + x);
					else if(j - x * (i - m) == K) dp[i][j] = max(dp[i][j], x);
				}
			}
		}
	}
	if(L + K < 0 || L + K >= MAXN * MAXN / 2) cout << "impossible\n";
	else if(dp[2 * m][L + K] < 0) cout << "impossible\n";
	else cout << dp[2 * m][L + K];
	return 0;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	10164 KB	Output is correct
2	Correct	15 ms	14132 KB	Output is correct
3	Correct	8 ms	6216 KB	Output is correct
4	Correct	69 ms	41700 KB	Output is correct
5	Correct	1388 ms	199832 KB	Output is correct
6	Correct	1497 ms	199888 KB	Output is correct
7	Correct	689 ms	199916 KB	Output is correct
8	Correct	1432 ms	200016 KB	Output is correct
9	Correct	2498 ms	200012 KB	Output is correct
10	Correct	208 ms	199980 KB	Output is correct
11	Correct	186 ms	199848 KB	Output is correct

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	10164 KB	Output is correct
2	Correct	15 ms	14132 KB	Output is correct
3	Correct	8 ms	6216 KB	Output is correct
4	Correct	69 ms	41700 KB	Output is correct
5	Correct	1388 ms	199832 KB	Output is correct
6	Correct	1497 ms	199888 KB	Output is correct
7	Correct	689 ms	199916 KB	Output is correct
8	Correct	1432 ms	200016 KB	Output is correct
9	Correct	2498 ms	200012 KB	Output is correct
10	Correct	208 ms	199980 KB	Output is correct
11	Correct	186 ms	199848 KB	Output is correct
12	Correct	13 ms	10196 KB	Output is correct
13	Correct	18 ms	14060 KB	Output is correct
14	Correct	9 ms	6144 KB	Output is correct
15	Correct	65 ms	41800 KB	Output is correct
16	Correct	1433 ms	200000 KB	Output is correct
17	Correct	1462 ms	199896 KB	Output is correct
18	Correct	676 ms	199928 KB	Output is correct
19	Correct	1447 ms	199892 KB	Output is correct
20	Correct	2499 ms	199916 KB	Output is correct
21	Correct	210 ms	199984 KB	Output is correct
22	Correct	189 ms	199928 KB	Output is correct
23	Execution timed out	5061 ms	369612 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

Subtask #3-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	41808 KB	Output is correct
2	Runtime error	873 ms	132548 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #3-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	41808 KB	Output is correct
2	Runtime error	873 ms	132548 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #4-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	41808 KB	Output is correct
2	Runtime error	873 ms	132548 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #4-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	10164 KB	Output is correct
2	Correct	15 ms	14132 KB	Output is correct
3	Correct	8 ms	6216 KB	Output is correct
4	Correct	69 ms	41700 KB	Output is correct
5	Correct	1388 ms	199832 KB	Output is correct
6	Correct	1497 ms	199888 KB	Output is correct
7	Correct	689 ms	199916 KB	Output is correct
8	Correct	1432 ms	200016 KB	Output is correct
9	Correct	2498 ms	200012 KB	Output is correct
10	Correct	208 ms	199980 KB	Output is correct
11	Correct	186 ms	199848 KB	Output is correct
12	Correct	67 ms	41808 KB	Output is correct
13	Runtime error	873 ms	132548 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-

Subtask #5-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	41808 KB	Output is correct
2	Runtime error	873 ms	132548 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #5-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	10164 KB	Output is correct
2	Correct	15 ms	14132 KB	Output is correct
3	Correct	8 ms	6216 KB	Output is correct
4	Correct	69 ms	41700 KB	Output is correct
5	Correct	1388 ms	199832 KB	Output is correct
6	Correct	1497 ms	199888 KB	Output is correct
7	Correct	689 ms	199916 KB	Output is correct
8	Correct	1432 ms	200016 KB	Output is correct
9	Correct	2498 ms	200012 KB	Output is correct
10	Correct	208 ms	199980 KB	Output is correct
11	Correct	186 ms	199848 KB	Output is correct
12	Correct	13 ms	10196 KB	Output is correct
13	Correct	18 ms	14060 KB	Output is correct
14	Correct	9 ms	6144 KB	Output is correct
15	Correct	65 ms	41800 KB	Output is correct
16	Correct	1433 ms	200000 KB	Output is correct
17	Correct	1462 ms	199896 KB	Output is correct
18	Correct	676 ms	199928 KB	Output is correct
19	Correct	1447 ms	199892 KB	Output is correct
20	Correct	2499 ms	199916 KB	Output is correct
21	Correct	210 ms	199984 KB	Output is correct
22	Correct	189 ms	199928 KB	Output is correct
23	Execution timed out	5061 ms	369612 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

Subtask #6-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	41808 KB	Output is correct
2	Runtime error	873 ms	132548 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #6-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	10164 KB	Output is correct
2	Correct	15 ms	14132 KB	Output is correct
3	Correct	8 ms	6216 KB	Output is correct
4	Correct	69 ms	41700 KB	Output is correct
5	Correct	1388 ms	199832 KB	Output is correct
6	Correct	1497 ms	199888 KB	Output is correct
7	Correct	689 ms	199916 KB	Output is correct
8	Correct	1432 ms	200016 KB	Output is correct
9	Correct	2498 ms	200012 KB	Output is correct
10	Correct	208 ms	199980 KB	Output is correct
11	Correct	186 ms	199848 KB	Output is correct
12	Correct	13 ms	10196 KB	Output is correct
13	Correct	18 ms	14060 KB	Output is correct
14	Correct	9 ms	6144 KB	Output is correct
15	Correct	65 ms	41800 KB	Output is correct
16	Correct	1433 ms	200000 KB	Output is correct
17	Correct	1462 ms	199896 KB	Output is correct
18	Correct	676 ms	199928 KB	Output is correct
19	Correct	1447 ms	199892 KB	Output is correct
20	Correct	2499 ms	199916 KB	Output is correct
21	Correct	210 ms	199984 KB	Output is correct
22	Correct	189 ms	199928 KB	Output is correct
23	Execution timed out	5061 ms	369612 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

Submission #792072

Compilation message