제출 #706879

#제출 시각아이디문제언어결과실행 시간메모리
706879ld_minh4354Bigger segments (IZhO19_segments)C++17
37 / 100
18 ms812 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pb push_back #define debug(x) cout<<#x<<": "<<x<<"\n" signed main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); // freopen("input.000","r",stdin); // freopen("output.000","w",stdout); // srand((unsigned)time(NULL)); // rand() int n,i,a[3005],j,pre[3005]; pair<int,int> dp[3005]; cin>>n; for (i=1;i<n+1;i++) cin>>a[i]; pre[1]=a[1]; for (i=2;i<n+1;i++) pre[i]=pre[i-1]+a[i]; dp[1]={1,-a[1]}; for (i=2;i<n+1;i++) { dp[i]={1,-pre[i]}; for (j=1;j<i;j++) if (-dp[j].se<=pre[i]-pre[j]) { dp[i]=max(dp[i], {dp[j].fi+1, -pre[i]+pre[j]}); } } // for (i=1;i<n+1;i++) cout<<dp[i].fi<<" "<<dp[i].se<<"\n"; cout<<dp[n].fi; }
#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...