Submission #1129443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129443		__algebra__	Bigger segments (IZhO19_segments)	C++20	100 / 100	73 ms	10408 KiB

segments

#include <bits/stdc++.h>
using namespace std;
using pp = pair<long long,long long>;
void run_case(){
    int n,dp=0;
    scanf("%d",&n);

    long long pre=0,mxn=0;
    vector<priority_queue<pp, vector<pp>, greater<pp>>> pq(2);
    
    function<void(int)> clear_pq = [&](const int &bit)->void{
        for(;!pq[bit].empty();pq[bit].pop());
    };

    pq[dp&1].emplace(pre+mxn,pre);

    for(int i=1,x;i<=n;++i){
        scanf("%d",&x);
        pre += x, mxn += x;
        if(pre >= pq[dp&1].top().first){
            mxn = pre - pq[dp&1].top().second;
            ++dp,clear_pq(dp&1);
        }
        for(;!pq[dp&1^1].empty() && pre >= pq[dp&1^1].top().first;pq[dp&1^1].pop()) mxn = min(mxn, pre - pq[dp&1^1].top().second);
        pq[dp&1].emplace(pre+mxn,pre);
    }
    printf("%d\n",dp);
}
int main(){
    #ifdef LOCAL 
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    
    int tc=1;
    for(;tc--;) run_case();
}

Compilation message (stderr)

segments.cpp: In function 'void run_case()':
segments.cpp:6:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |     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("%d",&x);
      |         ~~~~~^~~~~~~~~

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