Submission #1192897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192897		lopkus	Bigger segments (IZhO19_segments)	C++20	100 / 100	50 ms	15944 KiB

segments

#pragma GCC optimize("O3")
#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define in insert
#define fi first
#define se second
#define vl vector<ll>
#define all(v) v.begin(), v.end()
#define endl '\n'

using namespace std;
const int sz = 1e5 + 5; /// mind this
const int MAX = 1e6 + 123;
const int BL = 300;
const int lg = 20;
bool cmp(array<ll, 2> A, array<ll, 2> B){
    if(A[0] == B[0]){
        return A[1] > B[1];
    }
    return A[0] < B[0];
}
void solve(){
    ll n, i, j, ans = 0;
    cin >> n;
    vl v(n + 1), p(n + 1);
    vector<array<ll, 2>> dp(n + 1);
    p[0] = 0;
    for(i = 1; i <= n; i++){
        cin >> v[i];
        p[i] = p[i - 1] + v[i];
    }
    for(i = 1; i <= n; i++){
        dp[i] = {1, p[i]};
    }
    array<ll, 2> cur = {0, 0};
    for(i = 1; i <= n; i++){
        cur[1] += v[i];
        cur = max(cur, dp[i], cmp);
        ll lo = i + 1, hi = n, mid, best = n + 1;
        while(lo <= hi){
            mid = (lo + hi) >> 1;
            if((p[mid] - p[i]) >= cur[1]){
                best = mid;
                hi = mid - 1;
            }
            else{
                lo = mid + 1;
            }
        }
        if(best <= n){
            dp[best] = {cur[0] + 1, p[best] - p[i]};
        }
    }
    for(i = 1; i <= n; i++){
        ans = max(ans, dp[i][0]);
    }
    cout << ans << endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t = 1;
    // cin >> t;
    while(t--){
        solve();
    }   
}
/*
*/

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