제출 #1211995

#제출 시각아이디문제언어결과실행 시간메모리
1211995naelwbCigle (COI21_cigle)C++20
0 / 100
59 ms2376 KiB
#include <bits/stdc++.h> using namespace std; #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #pragma GCC optimize("unroll-loops") #pragma GCC optimize("Ofast") #define fi first #define se second #define pb push_back #define int long long #define mp make_pair #define pii pair<int, int> typedef long long ll; const int INF = 1e13; const int mxn = 2e5+5; const int mod = 1e9+7; inline int mul(int a, int b){return (a*b)%mod;} void solve(){ int n; cin >> n; int a[n+1]; vector<vector<int>> dp(n+2, vector<int>(n+2, 0LL)); for(int i = 1; i <= n; i++)cin>>a[i]; for(int j = 1; j <= n; j++){ for(int i = 1; i <= j; i++){ vector<int> pref(n+1, 0); pref[0] = 0; int cur = 0, id = i, val = 0; for(int k = i-1; k >= 1; k--){ pref[i-k] += pref[i-k-1] + a[k]; while(pref[i-k] > cur && id<=j){ cur += a[id]; ++id; } if(pref[i-k]==cur && id<=j && id>=i+1 && i>=3){ val++; } dp[i][j] = max(dp[i][j], dp[k-1][i-1] + val); } } } int ans = 0; for(int i = 1; i <= n; i++)ans = max(ans, *(max_element(dp[i].begin(), dp[i].end()))); cout << ans << endl; } int32_t main(){ fastio; int t = 1; // cin>>t; while(t--){ solve(); } }
#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...