Submission #520611

#TimeUsernameProblemLanguageResultExecution timeMemory
520611kartelCigle (COI21_cigle)C++14
100 / 100
260 ms98564 KiB
#include <bits/stdc++.h> //#include<ext/rope> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") //#pragma GCC optimize("-O3") //#pragma GCC target("avx2") #define in(x) freopen(x, "r", stdin) #define out(x) freopen(x, "w", stdout) #define F first #define S second #define pb push_back #define sz(x) int(x.size()) #define el '\n' #define all(x) x.begin(), x.end() using namespace std; //using namespace __gnu_pbds; //using namespace __gnu_cxx; typedef long long ll; typedef long double ld; typedef short int si; typedef unsigned long long ull; //typedef tree <ll, null_type, less <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set; const int N = 5005; int n, f[N][N], a[N]; int pf[N]; int main() { // cerr.precision(7); // cerr << fixed; ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0); // in("23.in"); // in("input.txt"); // out("output.txt"); // clock_t start = clock(); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { f[i][j] = -1e9; } } for (int i = 1; i <= n; i++) { f[1][i] = 0; } // for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { // sum_now += a[j]; for (int i = 1; i <= j; i++) { pf[i] = f[i][j]; } for (int i = 1; i <= j; i++) { pf[i] = max(pf[i - 1], pf[i]); } int pj = j; int sum = 0; int sum_was = 0; int cnt = 0; int mx = pf[j]; for (int k = j + 1; k <= n; k++) { f[j + 1][k] = mx; sum += a[k]; while (pj >= 1 && sum_was < sum) { sum_was += a[pj]; pj--; } if (pj > 0 && sum_was == sum) { cnt++; mx = max(mx, pf[pj] + cnt); } } } // } int ans = 0; for (int i = 1; i <= n; i++) { ans = max(ans, f[i][n]); } cout << ans; }
#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...