Submission #486854

#	Time	Username	Problem	Language	Result	Execution time	Memory
486854		SirCovidThe19th	Bigger segments (IZhO19_segments)	C++17	100 / 100	273 ms	44216 KiB

segments

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define f first
#define s second

const int mx = 5e5 + 5;

int n; ll pre[mx]; vector<int> ok[mx]; pair<int, ll> bst, dp[mx]; 

int main(){
    int n; cin >> n; 
    for (int i = 1; i <= n; i++) cin >> pre[i], pre[i] += pre[i - 1];
    ok[1].push_back(0);
    for (int i = 1, l = 0; i <= n; i++){
        for (int X : ok[i]) bst = max(bst, {dp[X].f + 1, X});
        dp[i] = {bst.f, pre[i] - pre[bst.s]};    
        int okPos = lower_bound(pre + 1, pre + n + 1, pre[i] + dp[i].s) - pre;
        ok[okPos].push_back(i);
    }
    cout<<dp[n].f<<endl;
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:16:21: warning: unused variable 'l' [-Wunused-variable]
   16 |     for (int i = 1, l = 0; i <= n; i++){
      |                     ^

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