Submission #520621

#TimeUsernameProblemLanguageResultExecution timeMemory
520621VimmerCigle (COI21_cigle)C++14
48 / 100
1096 ms218260 KiB
#include <bits/stdc++.h> #define in(x) freopen(x, "r", stdin) #define out(x) freopen(x, "w", stdout) #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-O3") #define F first #define S second #define PB push_back #define M ll(1e9 + 7) #define sz(x) (ll)x.size() #define N 1000500 #define pri(x) cout << x << endl #define endl '\n' #define all(x) (x).begin(), (x).end() #define _ << " " << using namespace std; //typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set; //using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef short int si; typedef unsigned long long ull; si f[5001][5001][2]; vector <int> was[5001]; int pr[5001]; si now[5001][5001][2]; int main() { istream::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); memset(f, -1, sizeof f); int n; cin >> n; int a[n]; si ans = 0; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) { pr[i] = a[i]; if (i) pr[i] += pr[i - 1]; } for (int l = 0; l < n; l++) { int sum = 0; for (int r = l; r < n; r++) { sum += a[r]; int L = r + 1, R = n - 1; while (L < R) { int md = (L + R) >> 1; if (pr[md] - pr[r] >= sum) R = md; else L = md + 1; } if (pr[L] - pr[r] == sum) { was[r].PB(L); } } } for (int i = 0; i < n; i++) sort(all(was[i])); memset(now, -1, sizeof now); for (int i = 0; i < n; i++) f[0][i][0] = 0; for (int r = 0; r < n; r++) for (int l = 0; l <= r; l++) for (int t = 0; t < 2; t++) { if (r) now[l][r][t] = max(now[l][r][t], now[l][r - 1][t]); f[l][r][t] = max(f[l][r][t], now[l][r][t]); if (f[l][r][t] != -1) { si kl = f[l][r][t]; int sm = pr[r], cur = 0; if (l) sm -= pr[l - 1]; for (auto nw : was[r]) { cur = pr[nw] - pr[r]; if (cur >= sm) { now[r + 1][nw][t ^ 1] = max(now[r + 1][nw][t ^ 1], si(kl)); break; } else { if (nw != n - 1) { kl++; now[r + 1][nw + 1][t ^ 1] = max(now[r + 1][nw + 1][t ^ 1], si(kl)); } ans = max(ans, kl); } } } } pri(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...