Submission #1204969

#TimeUsernameProblemLanguageResultExecution timeMemory
1204969ofozBigger segments (IZhO19_segments)C++17
37 / 100
1596 ms21456 KiB
#include <bits/stdc++.h> using namespace std; #define int long long vector<int> a; vector<int> prfx; vector< vector<int> > memo; // Compute prefix sum from l to r int getPrfx(int l, int r) { int left = (l == 0) ? 0 : prfx[l - 1]; int right = prfx[r]; return right - left; } // Custom comparison function bool compare(const vector<int>& s1, const vector<int>& s2) { if (s1[0] > s2[0]) return true; if (s1[0] < s2[0]) return false; return s1[1] < s2[1]; } // DP function vector<int> dp(int i) { if (i < 0) return vector<int>{1, 0}; if (memo[i][0] != -1) return memo[i]; vector<int> res = dp(i - 1); res[1] += a[i]; for (int j = 0; j < i; ++j) { vector<int> c = dp(j); int s = getPrfx(j + 1, i); if (s < c[1]) continue; c[1] = s; c[0] += 1; if (compare(c, res)) res = c; } memo[i] = res; return res; } signed main() { int n; cin >> n; a.resize(n); for (int i = 0; i < n; ++i) cin >> a[i]; prfx.resize(n); prfx[0] = a[1]; for (int i = 1; i < n; ++i) { prfx[i] = prfx[i - 1] + a[i]; } memo.assign(n, vector<int>(2, -1)); vector<int> result = dp(n - 1); cout << result[0] << endl; 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...