Submission #499845

#	Time	Username	Problem	Language	Result	Execution time	Memory
499845		reni	Bigger segments (IZhO19_segments)	C++14	13 / 100	1 ms	332 KiB

segments

#include<iostream>
#define endl '\n'
using namespace std;
long long pref[1000000], ans[1000000], sum[1000000];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long n,i,j, ch, pr, br=0, maxr=1, le, ri, mid;

    cin>>n;

    for(i=1;i<=n;i++)
    {
        cin>>ch;
        pref[i]=pref[i-1]+ch;
    }
    ans[1]=1;
    sum[1]=pref[1];

    for(i=2;i<=n;i++)
    {
        le=0;ri=i-1;int ind=-1;
        ans[i]=ans[i-1];sum[i]=sum[i-1]+pref[i]-pref[i-1];

        while(le<=ri)
        {
            mid=(le+ri)/2;
            if(sum[mid]<=pref[i]-pref[mid]){ind=mid;le=mid+1;}
            else ri=mid-1;
        }
          j=ind;
          //cout<<j<<endl;
          if(j<0)continue;

            if(sum[j]<=pref[i]-pref[j])
            {
                if(ans[j]+1>ans[i])
                {
                    ans[i]=ans[j]+1;
                    sum[i]=pref[i]-pref[j];
                }
                else if(ans[j]+1==ans[i])
                {
                    ans[i]=ans[j]+1;
                    sum[i]=min(sum[i],pref[i]-pref[j]);
                }
            }
       // cout<<ans[i]<<" "<<sum[i]<<endl;

    }
    cout<<ans[n]<<endl;

}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:11:26: warning: unused variable 'pr' [-Wunused-variable]
   11 |     long long n,i,j, ch, pr, br=0, maxr=1, le, ri, mid;
      |                          ^~
segments.cpp:11:30: warning: unused variable 'br' [-Wunused-variable]
   11 |     long long n,i,j, ch, pr, br=0, maxr=1, le, ri, mid;
      |                              ^~
segments.cpp:11:36: warning: unused variable 'maxr' [-Wunused-variable]
   11 |     long long n,i,j, ch, pr, br=0, maxr=1, le, ri, mid;
      |                                    ^~~~

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