제출 #374048

#제출 시각아이디문제언어결과실행 시간메모리
374048mariowongBigger segments (IZhO19_segments)C++14
37 / 100
5 ms512 KiB
#include <bits/stdc++.h> using namespace std; long long n,a[3005],pt; pair <long long,long long> dp[3005]; long long ps[3005],ans; int main(){ ios::sync_with_stdio(false); cin >> n; for (int i=1;i<=n;i++){ cin >> a[i]; ps[i]=ps[i-1]+a[i]; } pt=1; for (int i=1;i<=n;i++){ dp[i]=make_pair(ps[i],1); for (int j=i-1;j>=pt;j--){ if (ps[i]-ps[j] >= dp[j].first){ dp[i]=make_pair(ps[i]-ps[j],dp[j].second+1); pt=j; break; } } } cout << dp[n].second << "\n"; 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...