제출 #1003595

#제출 시각아이디문제언어결과실행 시간메모리
1003595ThegeekKnight16Cigle (COI21_cigle)C++17
0 / 100
1 ms1372 KiB
#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]; 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]); 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], mSuf); sumR += v[r]; } } int resp = 0; for (int i = 1; i <= N; i++) resp = max(resp, dp[i][N]); cout << resp << '\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...