Submission #1216970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216970		Hectorungo_18	Bigger segments (IZhO19_segments)	C++20	13 / 100	0 ms	328 KiB

segments

#include <bits/stdc++.h>
using namespace std;

string abc = "abcdefghijklmnopqrstuvwxyz";
// #define int long long

#define f first
#define s second


signed main() {
  int n;
  cin >> n;
  vector<int> v(n+1);
  // vector<vector<int>> dp(n+2, vector<int> (n+2, -1));
  // dp[0][]=0;
  vector<int> ps(n+1, 0);
  ps[0]=0;
  for(int i = 1; i <= n; i++) cin >> v[i];
  for(int i=1; i<= n;i++){
    ps[i]=ps[i-1]+v[i];
    // cout << i << " " << ps[i] << endl;
  }
  
  vector<pair<int,int>> dp(n+3, {0, 1e9+7});
  dp[0]={0, 0};
  dp[1]={1, v[1]};
  for(int i = 1; i <= n; i++){
    // cout << i << " " << dp[i].f << " " <<  dp[i].s <<endl;
    if(dp[i-1].f > dp[i].f){
      dp[i] =dp[i-1];
      dp[i].s+=v[i];
    }
    if(dp[i-1].f == dp[i].f && dp[i].f > dp[i-1].f+v[i]){
      dp[i] =dp[i-1];
      dp[i].s+=v[i];
    }


    int l = i+1, r = n;
    int b = -1;
    while(l <= r){
      // cout << l << " " << r <<endl;
      int m = (l+r+1)/2;
      if(ps[m]-ps[i] >= dp[i].s){
        b = m;
        if(r == m-1) break;
        r = m-1;
      }
      else{
        if(l == m) break;
        l = m;
      }
    }
    // cout << b << endl;
    if(b == -1) continue;
    else{
      if(dp[b].f <= dp[i].f){
        dp[b]= {dp[i].f+1, ps[b]-ps[i]};
      }
      else if(dp[b].f == dp[i].f+1 && ps[b]-ps[i] < dp[b].s){
        dp[b]= {dp[i].f+1, ps[b]-ps[i]};
      }
    }
    // cout << i << " " << dp[i].f << " " <<  dp[i].s <<endl;
  }

  int ans =0;
  

  cout << dp[n].f << endl;

}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27