제출 #497352

#제출 시각아이디문제언어결과실행 시간메모리
497352IerusBigger segments (IZhO19_segments)C++17
0 / 100
0 ms332 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize ("unroll-loops,Ofast,O3") #pragma GCC target("avx,avx2,fma") #define F first #define S second #define int long long #define sz(x) (int)x.size() #define pb push_back #define eb emplace_back #define all(x) (x).begin(),(x).end() const int E = 5e5+777; const long long inf = 1e18+777; const int N = 3e3+777; const int MOD = 1e9+7; int n, a[E], pref[E], dp[N][N]; int get(int l, int r){ return pref[r] - pref[l-1]; } signed main(){ ios_base::sync_with_stdio(0), cin.tie(0),cout.tie(0); cin >> n; for(int i = 1; i <= n; ++i){ cin >> a[i]; pref[i] = pref[i-1] + a[i]; } dp[1][1] = 1; for(int l = 1; l <= n; ++l){ for(int r = l; r <= n; ++r){ if(l == 1 && r == 1) continue; int mx = -1; for(int k = 1; k < l; ++k){ if(get(k, l-1) <= get(l, r)){ mx = max(mx, dp[k][l-1]); } } if(mx == -1){ dp[l][r] = mx; }else{ dp[l][r] = mx + 1; } } } for(int i = 1; i <= n; ++i){ for(int j = i; j <= n; ++j){ cerr << "{" << i << "," << j << "}: " << dp[i][j] << '\n'; } } int res = 0; for(int i = 1; i <= n; ++i){ res = max(res, dp[i][n]); } cout << res; }
#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...