| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 804333 |
2023-08-03T08:04:38 Z |
박상훈(#10101) |
Fun Palace (CCO18_fun) |
C++17 |
|
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);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
