oj.uz

Submission #804062

# Submission time Handle Problem Language Result Execution time Memory
804062 2023-08-03T07:00:15 Z 이온조(#10140) Fun Palace (CCO18_fun) C++17
3 / 25
 301 ms 323492 KB 
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

int A[1009], B[1009], L[2][20009][1009], R[2][20009][1009], C[2][2][1009][1009];
long long D[2][1009];

int main() {
	int N; scanf("%d%d", &N, &B[1]);
	for(int i=2; i<=N; i++) scanf("%d%d", &A[i-1], &B[i]);
	for(int i=1; i<=N; i++) L[0][0][i] = R[0][0][i] = i, L[1][0][i] = R[1][0][i] = 0;
	for(int c=1; c<=20000; c++) {
		for(int i=1; i<=N; i++) {
			if(A[i-1] + B[i] <= c) {
				L[0][c][i] = L[0][c][i-1];
				L[1][c][i] = L[1][c][i-1];
			}
			else if(B[i] < c) {
				L[0][c][i] = L[0][c - B[i]][i-1];
				L[1][c][i] = L[1][c - B[i]][i-1];
			}
			else if(B[i] == c) {
				L[0][c][i] = i-1;
				L[1][c][i] = 0;
			}
			else {
				L[0][c][i] = 0;
				L[1][c][i] = i;
			}
		}
		R[0][c][N] = N;
		for(int i=N-1; i>=1; i--) {
			if(A[i] + B[i+1] <= c) {
				R[0][c][i] = R[0][c][i+1];
				R[1][c][i] = R[1][c][i+1];
			}
			else if(A[i] < c) {
				R[0][c][i] = R[0][c - A[i]][i+1];
				R[1][c][i] = R[1][c - A[i]][i+1];
			}
			else if(A[i] == c) {
				R[0][c][i] = i+1;
				R[1][c][i] = 0;
			}
			else {
				R[0][c][i] = 0;
				R[1][c][i] = i;
			}
		}
		for(int i=1; i<=N; i++) for(int x=0; x<2; x++) for(int y=0; y<2; y++) {
			int l = L[x][c][i], r = R[y][c][i];
			if(l && l <= r) {
				C[x][y][l][r] = max(C[x][y][l][r], c);
			}
		}
	}
	D[0][0] = -INF;
	for(int i=1; i<=N; i++) for(int x=0; x<2; x++) for(int y=0; y<2; y++) for(int z=0; z<2; z++) for(int j=0; j<i; j++) {
		if(x == 0 && y == 0 && j != 0) D[z][i] = max(D[z][i], D[x][j] + C[y][z][j][i]);
		else D[z][i] = max(D[z][i], D[x][j] + C[y][z][j+1][i]);
	}
	printf("%lld", max(D[0][N], D[1][N]));
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:9:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  int N; scanf("%d%d", &N, &B[1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:10:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  for(int i=2; i<=N; i++) scanf("%d%d", &A[i-1], &B[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 237424 KB Output is correct
2 Correct 144 ms 316204 KB Output is correct
3 Correct 140 ms 316176 KB Output is correct
4 Correct 150 ms 316252 KB Output is correct
5 Correct 151 ms 316208 KB Output is correct
6 Correct 180 ms 316196 KB Output is correct
7 Correct 153 ms 316268 KB Output is correct
8 Correct 128 ms 237372 KB Output is correct
9 Correct 119 ms 237388 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 237408 KB Output is correct
2 Correct 148 ms 316208 KB Output is correct
3 Correct 157 ms 316156 KB Output is correct
4 Correct 155 ms 316228 KB Output is correct
5 Correct 150 ms 316280 KB Output is correct
6 Correct 119 ms 237384 KB Output is correct
7 Incorrect 301 ms 323492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 237424 KB Output is correct
2 Correct 144 ms 316204 KB Output is correct
3 Correct 140 ms 316176 KB Output is correct
4 Correct 150 ms 316252 KB Output is correct
5 Correct 151 ms 316208 KB Output is correct
6 Correct 180 ms 316196 KB Output is correct
7 Correct 153 ms 316268 KB Output is correct
8 Correct 128 ms 237372 KB Output is correct
9 Correct 119 ms 237388 KB Output is correct
10 Correct 151 ms 316244 KB Output is correct
11 Correct 147 ms 316260 KB Output is correct
12 Correct 164 ms 316292 KB Output is correct
13 Correct 115 ms 237324 KB Output is correct
14 Incorrect 180 ms 318488 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 237424 KB Output is correct
2 Correct 144 ms 316204 KB Output is correct
3 Correct 140 ms 316176 KB Output is correct
4 Correct 150 ms 316252 KB Output is correct
5 Correct 151 ms 316208 KB Output is correct
6 Correct 180 ms 316196 KB Output is correct
7 Correct 153 ms 316268 KB Output is correct
8 Correct 128 ms 237372 KB Output is correct
9 Correct 119 ms 237388 KB Output is correct
10 Correct 114 ms 237408 KB Output is correct
11 Correct 148 ms 316208 KB Output is correct
12 Correct 157 ms 316156 KB Output is correct
13 Correct 155 ms 316228 KB Output is correct
14 Correct 150 ms 316280 KB Output is correct
15 Correct 119 ms 237384 KB Output is correct
16 Incorrect 301 ms 323492 KB Output isn't correct
17 Halted 0 ms 0 KB -