제출 #1318999

#제출 시각아이디문제언어결과실행 시간메모리
1318999JohanBigger segments (IZhO19_segments)C++20
37 / 100
1594 ms3320 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
const int N = 2e5 + 5;
int a[N], dp[N][2], pr[N];
signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    pr[i] = pr[i - 1] + a[i];
    dp[i][0] = -1;
    dp[i][1] = INF;
  }
  dp[1][0] = 1;
  dp[1][1] = a[1];
  for(int i = 2; i <= n; i++){
    for(int j = i; j >= 0; j--){
      int sum = pr[i] - pr[j];
      if(dp[j][1] + pr[j] <= pr[i]){
        dp[i][1] = min(dp[i][1], sum);
        dp[i][0] = dp[j][0] + 1;
        break;
      }
    }
  }
  cout << dp[n][0] << endl;
}
#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...