Submission #520610

#TimeUsernameProblemLanguageResultExecution timeMemory
520610kartelCigle (COI21_cigle)C++14
0 / 100
1 ms316 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], 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[j] = -1e9; } // } // for (int i = 1; i <= n; i++) { // f[1][i] = 0; // } f[1] = 0; // for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { // sum_now += a[j]; pf[j] = max(pf[j - 1], f[j]); int pj = j; int sum = 0; int sum_was = 0; int cnt = 0; int mx = 0; for (int k = j + 1; k <= n; k++) { sum += a[k]; while (pj >= 1 && sum_was < sum) { sum_was += a[pj]; pj--; } // if (j + 1 == 9 && k == 12) { // cout << i << " " << j << " " << f[i][j] + cnt << el; // } if (sum_was == sum) { cnt++; mx = max(mx, pf[pj - 1] + cnt); } f[k] = max({f[k], mx, pf[j]}); } } // } // int ans = 0; cout << f[n]; }
#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...