oj.uz

답안 #792066

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
792066 2023-07-24T14:41:19 Z ToniB Uplifting Excursion (BOI22_vault) C++17
5 / 100
 2439 ms 144340 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -