Submission #499850

#	Time	Username	Problem	Language	Result	Execution time	Memory
499850		reni	Bigger segments (IZhO19_segments)	C++14	100 / 100	105 ms	16840 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, le, ri, mid;

    cin>>n;

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

    ans[1]=1;

    for(i=1;i<=n;i++)
    {

        ans[i]=max(ans[i-1],ans[i]);
        sum[i]=min(sum[i],sum[i-1]+pref[i]-pref[i-1]);

        le=0;ri=n+1;
        int ind=-1;

        while(le<ri-1)
        {
            mid=(le+ri)/2;
            if(sum[i]<=pref[mid]-pref[i]){ri=mid;}
            else {le=mid;}
        }
        if(ri>n)continue;


            if(ans[ri]<=ans[i]+1)
            {
                ans[ri]=ans[i]+1;
                sum[ri]=min(sum[ri],pref[ri]-pref[i]);

            }
        //cout<<ans[i]<<" "<<sum[i]<<endl;

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

}

Compilation message (stderr)

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

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