Submission #1096742

#TimeUsernameProblemLanguageResultExecution timeMemory
1096742stdfloatBigger segments (IZhO19_segments)C++17
27 / 100
1510 ms70992 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define ff first #define ss second #define pii pair<int, int> #define all(v) (v).begin(), (v).end() int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (auto &i : a) cin >> i; vector<vector<ll>> dp(n, vector<ll>(n, LLONG_MAX)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ll sm = 0; for (int k = i; k >= 0; k--) { sm += a[k]; if (j && k && dp[k - 1][j - 1] <= sm) { dp[i][j] = sm; break; } } if (!j) dp[i][0] = sm; } } for (int i = 0; i <= n; i++) if (i == n || dp[n - 1][i] == LLONG_MAX) return cout << i, 0; } // #include <bits/stdc++.h> // using namespace std; // using ll = long long; // int main() { // ios::sync_with_stdio(false); cin.tie(nullptr); // int n; // cin >> n; // vector<int> a(n); // for (auto &i : a) // cin >> i; // int mx = 1; // for (int mk = 0; mk < 1 << n; mk++) { // int cnt = 0; // ll pre_sm = -1, sm = 0; // for (int i = 0; i < n; i++) { // if (!i || (((mk >> i) & 1) != ((mk >> (i - 1)) & 1))) { // if (pre_sm > sm) { // cnt = 0; break; // } // cnt++; // pre_sm = sm; sm = 0; // } // sm += a[i]; // } // if (pre_sm <= sm) mx = max(mx, cnt); // } // cout << mx; // }
#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...