Submission #959840

#TimeUsernameProblemLanguageResultExecution timeMemory
959840ono_de206Cigle (COI21_cigle)C++14
100 / 100
342 ms332140 KiB
#include<bits/stdc++.h> using namespace std; #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define in insert #define all(x) x.begin(),x.end() #define pb push_back #define eb emplace_back #define ff first #define ss second #define int long long typedef long long ll; typedef vector<int> vi; typedef set<int> si; typedef multiset<int> msi; typedef pair<int, int> pii; typedef vector<pii> vpii; // typedef pair<int, int> P; template<typename T, typename U> ostream & operator << (ostream &out, const pair<T, U> &c) { out << c.first << ' ' << c.second; return out; } template<typename T> ostream & operator << (ostream &out, vector<T> &v) { const int sz = v.size(); for (int i = 0; i < sz; i++) { if (i) out << ' '; out << v[i]; } return out; } template<typename T> istream & operator >> (istream &in, vector<T> &v) { for (T &x : v) in >> x; return in; } template<typename T, typename U> istream & operator >> (istream &in, pair<T, U> &c) { in >> c.first; in >> c.second; return in; } template<typename T> void mxx(T &a, T b){if(b > a) a = b;} template<typename T> void mnn(T &a, T b){if(b < a) a = b;} const int mxn = 5e3 + 10, MXLOG = 22, mod = 1e9 + 7, P = 1181, D = 1523, N = 2500; const long long inf = 2e18 + 10; int dp[mxn][mxn], a[mxn], pos[mxn][mxn]; void go() { int n; cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i]; } for(int i = 1; i <= n; i++) { int l = i, sum = 0; for(int j = i + 1; j <= n; j++) { sum += a[j]; while(sum > 0 && l > 0) { sum -= a[l]; l--; } if(sum == 0) { pos[i][j] = l + 1; } } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { mxx(dp[i][j], dp[i][j - 1]); } int cnt = 0, mx = 0; for(int j = i + 1; j <= n; j++) { dp[j][i + 1] = mx; if(pos[i][j] > 1) { cnt++; mxx(mx, dp[i][pos[i][j] - 1] + cnt); } } } cout << dp[n][n] << endl; } signed main() { fast; int t = 1; // cin >> t; while(t--) { go(); } 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...