Submission #792069

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
792069	2023-07-24T14:42:59 Z	ToniB	Uplifting Excursion (BOI22_vault)	C++17	5 / 100	4306 ms	255220 KB

vault

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

int m, a[MAXN];
int dp[MAXN][MAXN * MAXN / 2];
long long L;
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	6612 KB	Output is correct
2	Correct	10 ms	9172 KB	Output is correct
3	Correct	6 ms	4080 KB	Output is correct
4	Correct	46 ms	26924 KB	Output is correct
5	Correct	1097 ms	128292 KB	Output is correct
6	Correct	1183 ms	128464 KB	Output is correct
7	Correct	516 ms	128352 KB	Output is correct
8	Correct	1171 ms	128316 KB	Output is correct
9	Correct	2047 ms	128324 KB	Output is correct
10	Correct	137 ms	128268 KB	Output is correct
11	Correct	130 ms	128348 KB	Output is correct

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	6612 KB	Output is correct
2	Correct	10 ms	9172 KB	Output is correct
3	Correct	6 ms	4080 KB	Output is correct
4	Correct	46 ms	26924 KB	Output is correct
5	Correct	1097 ms	128292 KB	Output is correct
6	Correct	1183 ms	128464 KB	Output is correct
7	Correct	516 ms	128352 KB	Output is correct
8	Correct	1171 ms	128316 KB	Output is correct
9	Correct	2047 ms	128324 KB	Output is correct
10	Correct	137 ms	128268 KB	Output is correct
11	Correct	130 ms	128348 KB	Output is correct
12	Correct	9 ms	6604 KB	Output is correct
13	Correct	10 ms	9172 KB	Output is correct
14	Correct	6 ms	4112 KB	Output is correct
15	Correct	53 ms	26904 KB	Output is correct
16	Correct	1113 ms	128372 KB	Output is correct
17	Correct	1192 ms	128320 KB	Output is correct
18	Correct	530 ms	128312 KB	Output is correct
19	Correct	1176 ms	128320 KB	Output is correct
20	Correct	2017 ms	128280 KB	Output is correct
21	Correct	137 ms	128380 KB	Output is correct
22	Correct	131 ms	128332 KB	Output is correct
23	Correct	4306 ms	255164 KB	Output is correct
24	Incorrect	4235 ms	255220 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	57 ms	27024 KB	Output is correct
2	Runtime error	754 ms	85152 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	57 ms	27024 KB	Output is correct
2	Runtime error	754 ms	85152 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	57 ms	27024 KB	Output is correct
2	Runtime error	754 ms	85152 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	9 ms	6612 KB	Output is correct
2	Correct	10 ms	9172 KB	Output is correct
3	Correct	6 ms	4080 KB	Output is correct
4	Correct	46 ms	26924 KB	Output is correct
5	Correct	1097 ms	128292 KB	Output is correct
6	Correct	1183 ms	128464 KB	Output is correct
7	Correct	516 ms	128352 KB	Output is correct
8	Correct	1171 ms	128316 KB	Output is correct
9	Correct	2047 ms	128324 KB	Output is correct
10	Correct	137 ms	128268 KB	Output is correct
11	Correct	130 ms	128348 KB	Output is correct
12	Correct	57 ms	27024 KB	Output is correct
13	Runtime error	754 ms	85152 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	57 ms	27024 KB	Output is correct
2	Runtime error	754 ms	85152 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	9 ms	6612 KB	Output is correct
2	Correct	10 ms	9172 KB	Output is correct
3	Correct	6 ms	4080 KB	Output is correct
4	Correct	46 ms	26924 KB	Output is correct
5	Correct	1097 ms	128292 KB	Output is correct
6	Correct	1183 ms	128464 KB	Output is correct
7	Correct	516 ms	128352 KB	Output is correct
8	Correct	1171 ms	128316 KB	Output is correct
9	Correct	2047 ms	128324 KB	Output is correct
10	Correct	137 ms	128268 KB	Output is correct
11	Correct	130 ms	128348 KB	Output is correct
12	Correct	9 ms	6604 KB	Output is correct
13	Correct	10 ms	9172 KB	Output is correct
14	Correct	6 ms	4112 KB	Output is correct
15	Correct	53 ms	26904 KB	Output is correct
16	Correct	1113 ms	128372 KB	Output is correct
17	Correct	1192 ms	128320 KB	Output is correct
18	Correct	530 ms	128312 KB	Output is correct
19	Correct	1176 ms	128320 KB	Output is correct
20	Correct	2017 ms	128280 KB	Output is correct
21	Correct	137 ms	128380 KB	Output is correct
22	Correct	131 ms	128332 KB	Output is correct
23	Correct	4306 ms	255164 KB	Output is correct
24	Incorrect	4235 ms	255220 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	57 ms	27024 KB	Output is correct
2	Runtime error	754 ms	85152 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	9 ms	6612 KB	Output is correct
2	Correct	10 ms	9172 KB	Output is correct
3	Correct	6 ms	4080 KB	Output is correct
4	Correct	46 ms	26924 KB	Output is correct
5	Correct	1097 ms	128292 KB	Output is correct
6	Correct	1183 ms	128464 KB	Output is correct
7	Correct	516 ms	128352 KB	Output is correct
8	Correct	1171 ms	128316 KB	Output is correct
9	Correct	2047 ms	128324 KB	Output is correct
10	Correct	137 ms	128268 KB	Output is correct
11	Correct	130 ms	128348 KB	Output is correct
12	Correct	9 ms	6604 KB	Output is correct
13	Correct	10 ms	9172 KB	Output is correct
14	Correct	6 ms	4112 KB	Output is correct
15	Correct	53 ms	26904 KB	Output is correct
16	Correct	1113 ms	128372 KB	Output is correct
17	Correct	1192 ms	128320 KB	Output is correct
18	Correct	530 ms	128312 KB	Output is correct
19	Correct	1176 ms	128320 KB	Output is correct
20	Correct	2017 ms	128280 KB	Output is correct
21	Correct	137 ms	128380 KB	Output is correct
22	Correct	131 ms	128332 KB	Output is correct
23	Correct	4306 ms	255164 KB	Output is correct
24	Incorrect	4235 ms	255220 KB	Output isn't correct
25	Halted	0 ms	0 KB	-

Submission #792069

Compilation message