Submission #499832

#	Time	Username	Problem	Language	Result	Execution time	Memory
499832		reni	Bigger segments (IZhO19_segments)	C++14	37 / 100	1556 ms	2580 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;

    cin>>n;

    for(i=1;i<=n;i++)
    {
        cin>>ch;
        pref[i]=pref[i-1]+ch;
    }
    for(i=1;i<=n;i++)
    {
        for(j=i-1;j>=0;j--)
        {
            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[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;
      |                          ^~
segments.cpp:11:30: warning: unused variable 'br' [-Wunused-variable]
   11 |     long long n,i,j, ch, pr, br=0, maxr=1;
      |                              ^~
segments.cpp:11:36: warning: unused variable 'maxr' [-Wunused-variable]
   11 |     long long n,i,j, ch, pr, br=0, maxr=1;
      |                                    ^~~~

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