Submission #792066

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
792066	2023-07-24T14:41:19 Z	ToniB	Uplifting Excursion (BOI22_vault)	C++17	5 / 100	2439 ms	144340 KB

vault

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

int m, L, a[MAXN];
int dp[MAXN][MAXN * MAXN / 2];

int main(){
	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	9 ms	3796 KB	Output is correct
2	Correct	6 ms	5320 KB	Output is correct
3	Correct	5 ms	2388 KB	Output is correct
4	Correct	29 ms	15336 KB	Output is correct
5	Correct	68 ms	72660 KB	Output is correct
6	Correct	663 ms	72544 KB	Output is correct
7	Correct	295 ms	72632 KB	Output is correct
8	Correct	647 ms	72604 KB	Output is correct
9	Correct	1123 ms	72604 KB	Output is correct
10	Correct	75 ms	72616 KB	Output is correct
11	Correct	67 ms	72580 KB	Output is correct

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	3796 KB	Output is correct
2	Correct	6 ms	5320 KB	Output is correct
3	Correct	5 ms	2388 KB	Output is correct
4	Correct	29 ms	15336 KB	Output is correct
5	Correct	68 ms	72660 KB	Output is correct
6	Correct	663 ms	72544 KB	Output is correct
7	Correct	295 ms	72632 KB	Output is correct
8	Correct	647 ms	72604 KB	Output is correct
9	Correct	1123 ms	72604 KB	Output is correct
10	Correct	75 ms	72616 KB	Output is correct
11	Correct	67 ms	72580 KB	Output is correct
12	Correct	8 ms	3796 KB	Output is correct
13	Correct	6 ms	5336 KB	Output is correct
14	Correct	3 ms	2388 KB	Output is correct
15	Correct	32 ms	15308 KB	Output is correct
16	Correct	64 ms	72564 KB	Output is correct
17	Correct	733 ms	72572 KB	Output is correct
18	Correct	301 ms	72524 KB	Output is correct
19	Correct	690 ms	72640 KB	Output is correct
20	Correct	1146 ms	72536 KB	Output is correct
21	Correct	76 ms	72540 KB	Output is correct
22	Correct	91 ms	72552 KB	Output is correct
23	Correct	120 ms	144340 KB	Output is correct
24	Incorrect	2439 ms	144260 KB	Output isn't correct
25	Halted	0 ms	0 KB	-

Subtask #3-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	15308 KB	Output is correct
2	Incorrect	55 ms	43868 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	15308 KB	Output is correct
2	Incorrect	55 ms	43868 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	15308 KB	Output is correct
2	Incorrect	55 ms	43868 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	3796 KB	Output is correct
2	Correct	6 ms	5320 KB	Output is correct
3	Correct	5 ms	2388 KB	Output is correct
4	Correct	29 ms	15336 KB	Output is correct
5	Correct	68 ms	72660 KB	Output is correct
6	Correct	663 ms	72544 KB	Output is correct
7	Correct	295 ms	72632 KB	Output is correct
8	Correct	647 ms	72604 KB	Output is correct
9	Correct	1123 ms	72604 KB	Output is correct
10	Correct	75 ms	72616 KB	Output is correct
11	Correct	67 ms	72580 KB	Output is correct
12	Correct	27 ms	15308 KB	Output is correct
13	Incorrect	55 ms	43868 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #5-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	15308 KB	Output is correct
2	Incorrect	55 ms	43868 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #5-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	3796 KB	Output is correct
2	Correct	6 ms	5320 KB	Output is correct
3	Correct	5 ms	2388 KB	Output is correct
4	Correct	29 ms	15336 KB	Output is correct
5	Correct	68 ms	72660 KB	Output is correct
6	Correct	663 ms	72544 KB	Output is correct
7	Correct	295 ms	72632 KB	Output is correct
8	Correct	647 ms	72604 KB	Output is correct
9	Correct	1123 ms	72604 KB	Output is correct
10	Correct	75 ms	72616 KB	Output is correct
11	Correct	67 ms	72580 KB	Output is correct
12	Correct	8 ms	3796 KB	Output is correct
13	Correct	6 ms	5336 KB	Output is correct
14	Correct	3 ms	2388 KB	Output is correct
15	Correct	32 ms	15308 KB	Output is correct
16	Correct	64 ms	72564 KB	Output is correct
17	Correct	733 ms	72572 KB	Output is correct
18	Correct	301 ms	72524 KB	Output is correct
19	Correct	690 ms	72640 KB	Output is correct
20	Correct	1146 ms	72536 KB	Output is correct
21	Correct	76 ms	72540 KB	Output is correct
22	Correct	91 ms	72552 KB	Output is correct
23	Correct	120 ms	144340 KB	Output is correct
24	Incorrect	2439 ms	144260 KB	Output isn't correct
25	Halted	0 ms	0 KB	-

Subtask #6-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	15308 KB	Output is correct
2	Incorrect	55 ms	43868 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #6-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	3796 KB	Output is correct
2	Correct	6 ms	5320 KB	Output is correct
3	Correct	5 ms	2388 KB	Output is correct
4	Correct	29 ms	15336 KB	Output is correct
5	Correct	68 ms	72660 KB	Output is correct
6	Correct	663 ms	72544 KB	Output is correct
7	Correct	295 ms	72632 KB	Output is correct
8	Correct	647 ms	72604 KB	Output is correct
9	Correct	1123 ms	72604 KB	Output is correct
10	Correct	75 ms	72616 KB	Output is correct
11	Correct	67 ms	72580 KB	Output is correct
12	Correct	8 ms	3796 KB	Output is correct
13	Correct	6 ms	5336 KB	Output is correct
14	Correct	3 ms	2388 KB	Output is correct
15	Correct	32 ms	15308 KB	Output is correct
16	Correct	64 ms	72564 KB	Output is correct
17	Correct	733 ms	72572 KB	Output is correct
18	Correct	301 ms	72524 KB	Output is correct
19	Correct	690 ms	72640 KB	Output is correct
20	Correct	1146 ms	72536 KB	Output is correct
21	Correct	76 ms	72540 KB	Output is correct
22	Correct	91 ms	72552 KB	Output is correct
23	Correct	120 ms	144340 KB	Output is correct
24	Incorrect	2439 ms	144260 KB	Output isn't correct
25	Halted	0 ms	0 KB	-

Submission #792066

Compilation message