# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1003600 | 2024-06-20T13:49:15 Z | ThegeekKnight16 | Cigle (COI21_cigle) | C++17 | 2 ms | 1372 KB |
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N; cin >> N; vector<int> v(N+1); for (int i = 1; i <= N; i++) cin >> v[i]; v[0] = 0x3f3f3f3f; vector<vector<int>> dp(N+1, vector<int>(N+1)); for (int l = 2; l <= N; l++) { vector<int> prefdp(N+1); for (int k = 1; k < l; k++) prefdp[k] = max(prefdp[k-1], dp[k][l-1]); // cerr << "l: " << l << '\n'; int sumL = v[l-1], sumR = 0, p = l-1, inters = 0, mSuf = 0; for (int r = l; r <= N; r++) { while (p >= 1 && sumL <= sumR) { if (sumL == sumR) inters++; sumL += v[--p]; mSuf = max(mSuf, dp[p][l-1] + inters); } dp[l][r] = max(prefdp[p] + inters, mSuf); sumR += v[r]; // cerr << dp[l][r] << " "; } // cerr << '\n'; } int resp = 0; for (int i = 1; i <= N; i++) resp = max(resp, dp[i][N]); cout << resp << '\n'; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Incorrect | 0 ms | 348 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Incorrect | 0 ms | 348 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 1372 KB | Output is correct |
2 | Incorrect | 1 ms | 1372 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Incorrect | 0 ms | 348 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Incorrect | 0 ms | 348 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |