제출 #936601

#제출 시각아이디문제언어결과실행 시간메모리
936601AiperiiiBigger segments (IZhO19_segments)C++14
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> #define int long long #define ff first #define ss second #define pb push_back #define all(x) x.begin(),x.end() using namespace std; signed main(){ ios_base::sync_with_stdio(); cin.tie(0);cout.tie(0); int n; cin>>n; vector <int> a(n+1),p(n+1); for(int i=1;i<=n;i++)cin>>a[i]; int ans=0; int dp[n+1][n+1]; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ dp[i][j]=1e18; } } for(int i=1;i<=n;i++){ p[i]=p[i-1]+a[i]; dp[1][i]=p[i]; } for(int i=2;i<=n;i++){ for(int j=i;j<=n;j++){ for(int k=i;k<=j;k++){ if(dp[i-1][k-1]<=p[j]-p[k-1])dp[i][j]=min(dp[i][j],p[j]-p[k-1]); } if(j==n){ if(dp[i][j]==1e18)break; ans=i; } } } cout<<ans<<"\n"; } /* 4 2 3 1 7 5 6 2 3 9 13 3 3 1 2 5 1 12 11 46 47 */
#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...