Submission #871388

#TimeUsernameProblemLanguageResultExecution timeMemory
871388Trisanu_DasTortoise (CEOI21_tortoise)C++17
48 / 100
281 ms430928 KiB
#include <bits/stdc++.h> using namespace std; int n, arr[302], sum[302], DP[603][302][302][2], ans; int main(){ cin >> n; for(int i=1; i<=n; i++){ cin >> arr[i]; sum[i] = sum[i-1]; if(arr[i] > 0) sum[i] += arr[i]; } for(int i=0; i<=n+n+1; i++) for(int j=0; j<=n; j++) for(int k=0; k<=n; k++) DP[i][j][k][0] = DP[i][j][k][1] = 1e9; DP[0][1][0][0] = 0; for(int t=0; t<=n+n+1; t++){ for(int i=1; i<=n; i++){ for(int j=0; j<=n; j++){ for(int c=0; c<2; c++) if(DP[t][i][j][c] < 1e9) ans = max(ans, j); if(arr[i] == -1) DP[t][i][j][0] = min(DP[t][i][j][0], DP[t][i][j][1]); if(arr[i] > 0 && DP[t][i][j][0] < sum[i] && i+i-2 >= t) DP[t][i][j+1][1] = min(DP[t][i][j+1][1], max(DP[t][i][j][0], sum[i-1])+1); for(int c=0; c<2; c++){ DP[t+1][i-1][j][c] = min(DP[t+1][i-1][j][c], DP[t][i][j][c]); DP[t+1][i+1][j][c] = min(DP[t+1][i+1][j][c], DP[t][i][j][c]); } } } } cout << sum[n] - ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...