Submission #299763

#	Time	Username	Problem	Language	Result	Execution time	Memory
299763		dantoh000	Bigger segments (IZhO19_segments)	C++14	100 / 100	224 ms	22100 KiB

segments

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll, int> li;
ii dp[500005];
int n;
ll p[500005];
ll k[500005];
priority_queue<li, vector<li>, greater<li> > pq;
int main(){
    scanf("%d",&n);
    pq.push({0,0});
    ii best = {0,0};
    for (int i = 1; i <= n; i++){
        scanf("%lld",&p[i]);
        p[i]+=p[i-1];
        /*int j;
        for (j = i-1; j >= 0; j--){
            if (p[i] >= k[j]) break;
        }*/

        li last;
        while (pq.size() && pq.top().fi <= p[i]){
            best = max(best,{dp[pq.top().se].fi,pq.top().se});
            last = pq.top(); pq.pop();
        }

        pq.push(last);
        int j = best.se;
        dp[i] = {dp[j].fi+1, j};
        k[i] = 2*p[i]-p[j];
        //printf("%lld: ",2*p[i]-p[j]);
        pq.push({k[i],i});
    }
    printf("%d",dp[n].fi);
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   14 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
segments.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |         scanf("%lld",&p[i]);
      |         ~~~~~^~~~~~~~~~~~~~

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