Submission #336069

#	Time	Username	Problem	Language	Result	Execution time	Memory
336069		ivan_tudor	Bigger segments (IZhO19_segments)	C++14	100 / 100	151 ms	13036 KiB

segments

#include<bits/stdc++.h>
using namespace std;
const int N =5*1e5+ 5;
long long spart[N];
int dp[N], poz[N];
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>spart[i];
    spart[i] += spart[i-1];
  }
  for(int i=1 ;i<=n;i++){
    poz[i] = max(poz[i], poz[i-1]);
    dp[i] = dp[poz[i]] + 1;
    long long sm = spart[i] - spart[poz[i]];
    int pas = i;
    for(int p2 = 1<<20; p2>0;p2>>=1){
      if(pas + p2<=n && spart[pas + p2] - spart[i] <sm)
        pas+=p2;
    }
    poz[pas + 1] = i;
  }
  cout<<dp[n];
  return 0;
}

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