# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
417378 | 2021-06-03T15:50:48 Z | doowey | Cigle (COI21_cigle) | C++14 | 3 ms | 2764 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define fi first #define se second #define mp make_pair #define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 5010; int dp[N][N]; int D[N]; bool mark[N]; int main(){ fastIO; int n; cin >> n; for(int i = 1; i <= n; i ++ ){ cin >> D[i]; } int pp; int cum; int cur; int outp = 0; int pap = 0; int dap; int val = 0; int total; for(int cut = 2; cut <= n; cut ++ ){ for(int ash = 2; ash <= cut - 1; ash ++ ){ dp[ash][cut - 1] = max(dp[ash][cut - 1], dp[ash-1][cut-1]); } cur = 0; cum = 0; pp = cut; dap = cut - 1; val = 0; total = 0; for(int go = cut; go <= n; go ++ ){ dp[cut][go] = dp[dap][cut - 1] + val; if(go == n) outp = max(outp, dp[cut][go]); cur += D[go]; while(pp > 1 && cum < cur){ pp --; cum += D[pp]; } if(cum == cur){ total ++ ; if(pp - 1 >= dap) val ++ ; else{ if(dp[pp - 1][cut - 1] + total >= dp[dap][cut - 1] + val){ val = total; dap = pp - 1; } } } } } cout << outp << "\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Incorrect | 1 ms | 460 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Incorrect | 1 ms | 460 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 2764 KB | Output is correct |
2 | Incorrect | 3 ms | 2764 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Incorrect | 1 ms | 460 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Incorrect | 1 ms | 460 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |