oj.uz

Submission #804333

# Submission time Handle Problem Language Result Execution time Memory
804333 2023-08-03T08:04:38 Z 박상훈(#10101) Fun Palace (CCO18_fun) C++17
3 / 25
 1000 ms 3412 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr int INF = 1e9 + 100;

int n;
int a[1010], b[1010];

int dp[2][1010][1010];

int main(){
	scanf("%d", &n);
	scanf("%d", b);

	for (int i=1;i<=n-1;i++) scanf("%d %d", a+i, b+i);

	int mx = max(*max_element(a+1, a+n), *max_element(b, b+n)) * 2;
	
	for (int j=0;j<=mx;j++) fill(dp[1][j], dp[1][j]+mx, -INF);
	for (int k=0;k<b[0];k++) dp[1][b[0]][k] = k;

	for (int i=2;i<=n;i++){
		int z = i&1;
		for (int j=0;j<=mx;j++) fill(dp[z][j], dp[z][j]+mx, -INF);

		for (int cap=0;cap<=mx;cap++){
			for (int cur=0;cur<cap;cur++) if (dp[z^1][cap][cur] >= 0){
				if (cur < a[i-1]){
					int ncap = max(b[i-1] + (a[i-1]-cur), cap-cur);
					ncap = min(ncap, b[i-1] + (cap-cur));
					for (int nxt=0;nxt<ncap;nxt++){
						int r = -1;

						if (nxt < b[i-1]) r = nxt;
						else r = nxt + cur;

						dp[z][ncap][r] = max(dp[z][ncap][r], dp[z^1][cap][cur] + nxt);
					} 
				}

				else{
					int lim = cap-cur;
					for (int nxt=0;nxt<lim;nxt++){
						int r = -1, ncap = -1;
						if (cur-a[i-1] + nxt < b[i-1]) r = cur-a[i-1] + nxt, ncap = cap - a[i-1];
						else r = cur + nxt, ncap = cap;

						dp[z][ncap][r] = max(dp[z][ncap][r], dp[z^1][cap][cur] + nxt);
					} 
				}
			}
		}
	}

	int ans = -INF;
	for (int j=0;j<=mx;j++) ans = max(ans, *max_element(dp[n&1][j], dp[n&1][j]+mx));

	printf("%d\n", ans);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
Main.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d", b);
      |  ~~~~~^~~~~~~~~
Main.cpp:17:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  for (int i=1;i<=n-1;i++) scanf("%d %d", a+i, b+i);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 616 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 1236 KB Output is correct
14 Execution timed out 1080 ms 3412 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -