Submission #467158

#	Time	Username	Problem	Language	Result	Execution time	Memory
467158		theconfusedguy	Bigger segments (IZhO19_segments)	C++14	13 / 100	1 ms	312 KiB

segments

#include <bits/stdc++.h>
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);

using namespace std;


typedef long long int lli;
typedef vector<int> vi;
typedef vector<long long int> vll;

const int mod = 1000000007;

int binarySearch(lli arr[], int N, int end, vll& prefSums, vll& prevMinimalSums ){
    int low = 0, high = end - 1;
    int ansIdx = 0;
    while( low <= high ){
        int mid = ( high - low ) / 2 + low;
        lli currSum = prefSums[end] - prefSums[mid];
        if( currSum >= prevMinimalSums[mid] ){
            ansIdx = mid;
            low = mid + 1;
        }
        else{
            high = mid - 1;
        }
    }
    return ansIdx;
}


int main(){
    SPEED;

    int N; cin >> N;
    lli arr[N+1];
    for( int i = 1; i <= N; i++ ) cin >> arr[i];
    vll dp(N+2, 0), prevMinimalSum(N+2, 0), prefSums(N+2, 0);
    for( int i = 1; i <= N; i++ ){
        prefSums[i] = prefSums[i-1] + arr[i];
    }
    
    dp[1] = 1;
    prevMinimalSum[1] = arr[1];

    for( int i = 2; i <= N; i++ ){
        int idx = binarySearch(arr, N, i, prefSums, prevMinimalSum );
        dp[i] = dp[idx] + 1;
        prevMinimalSum[i] = prefSums[i] - prefSums[idx];
    }

    cout << dp[N] << endl;
    return 0;
}

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