Submission #371408

#	Time	Username	Problem	Language	Result	Execution time	Memory
371408		nicolaalexandra	Bigger segments (IZhO19_segments)	C++14	0 / 100	1 ms	364 KiB

segments

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

int v[DIM],dp[DIM],poz[DIM];
long long sp[DIM];
int n,i;

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=n;i++){
        cin>>v[i];
        sp[i] = sp[i-1] + v[i];
    }

    dp[1] = 1;
    for (i=2;i<=n;i++){

        dp[i] = dp[i-1];
        poz[i] = poz[i-1];

        int st = 1, dr = i, sol = 0;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (sp[i] - sp[mid-1] >= sp[mid-1] - sp[poz[mid-1]]){
                st = mid+1;
                sol = mid;
            } else dr = mid-1;
        }

        if (dp[sol-1] + 1 > dp[i]){
            dp[i] = dp[sol-1] + 1;
            poz[i] = sol-1;
        }

    }

    cout<<dp[n];

    return 0;
}

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