Submission #341887

#	Time	Username	Problem	Language	Result	Execution time	Memory
341887		katearima	Bigger segments (IZhO19_segments)	C++14	0 / 100	1 ms	384 KiB

segments

#include <bits/stdc++.h>
//#define int long long
#define sum  first
#define ind second
using namespace std;
const int N=500005;
int a[N],sums[N], oldS, n;
int ans[N];
priority_queue<pair<int, int> , vector<pair<int, int>> , greater<pair<int, int>>> pq;
main(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    sums[0]=a[0];
    for(int i=1; i<n; i++){
        sums[i]=a[i]+sums[i-1];
    }
    int sp=0; // starting point of segment
    for(int i=0; i<n; i++){
      while(pq.size()!=0 && pq.top().sum <= sums[i]){
            int j=pq.top().ind;
            if(ans[j]>ans[sp]) sp=j;
            if(ans[j]==ans[sp]) sp=max(j, sp);
            pq.pop();

      }
       ans[i] = ans[sp]+1;
       pq.push(make_pair(2*sums[i]-sums[sp-1], i));
    }
    cout<<ans[n-1]<<endl;
}

Compilation message (stderr)

segments.cpp:10:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 | main(){
      |      ^

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