Submission #1112342

#TimeUsernameProblemLanguageResultExecution timeMemory
1112342JelalTkmBigger segments (IZhO19_segments)C++17
13 / 100
5 ms2384 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC target ("sse4") using namespace std; #define int long long int const int N = 3e5 + 10; const int md = 1e9 + 7; const int INF = 1e18; int32_t main(int32_t argc, char *argv[]) { ios::sync_with_stdio(false); cin.tie(nullptr); int T = 1; // cin >> T; while (T--) { int n; cin >> n; vector<int> a(n + 1), pref(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i]; pref[i] = pref[i - 1] + a[i]; } vector<vector<int>> dp(n + 1, vector<int> (n + 1, INF)); dp[0][0] = 0; int ans = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { int l = -1, r = i; while (r - l > 1) { int mid = (l + r) >> 1; if (j - 1 > mid || dp[mid][j - 1] == INF) { l = mid; continue; } if (dp[mid][j - 1] <= pref[i] - pref[mid]) { dp[i][j] = min(dp[i][j], pref[i] - pref[mid]); l = mid; } else r = mid; } if (i == n && dp[i][j] != INF) ans = max(ans, j); } } 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...