Submission #586086

#TimeUsernameProblemLanguageResultExecution timeMemory
586086MilosMilutinovicCigle (COI21_cigle)C++14
100 / 100
240 ms98512 KiB
/** * author: wxhtzdy * created: 29.06.2022 21:43:16 **/ #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } a[0] = 0; vector<long long> pref(n + 1); for (int i = 0; i < n; i++) { pref[i + 1] = pref[i] + a[i]; } vector<vector<int>> dp(n + 1, vector<int>(n + 1)); for (int l = 1; l <= n; l++) { int ptr = l - 1; long long t = pref[ptr] - pref[ptr - 1]; auto Find = [&](long long x) { while (ptr > 1 && x > t) { ptr -= 1; t += pref[ptr] - pref[ptr - 1]; } return (x == t ? ptr : 0); }; vector<int> pref_mx(n + 1); for (int i = 0; i < l; i++) { pref_mx[i + 1] = max(pref_mx[i], dp[i][l - 1]); } int ft = 0; for (int r = l; r <= n; r++) { dp[l][r] = dp[l][r - 1]; if (l < r) { long long s = pref[r - 1] - pref[l - 1]; int at = Find(s); if (at >= 1) { ft += 1; dp[l][r] = max(dp[l][r], ft + pref_mx[at]); } } } } int ans = 0; for (int i = 1; i <= n; i++) { ans = max(ans, dp[i][n]); } cout << ans << '\n'; return 0; }
#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...