Submission #1112375

#TimeUsernameProblemLanguageResultExecution timeMemory
1112375JelalTkmBigger segments (IZhO19_segments)C++17
27 / 100
1562 ms70984 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++) { dp[i][1] = pref[i]; for (int j = 2; j <= i; j++) { for (int k = i - 1; k >= 1; k--) { if (dp[k][j - 1] <= pref[i] - pref[k]) { dp[i][j] = pref[i] - pref[k]; break; } } 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...