제출 #467301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
467301		theconfusedguy	Bigger segments (IZhO19_segments)	C++14	100 / 100	118 ms	18876 KiB

segments

#include <bits/stdc++.h>
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;


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

const int mod = 1000000007;


int main(){
    SPEED;

    int N; cin >> N;
    vll arr(N+2), pref(N+2), dp(N+2);
    vi best(N+2);
    for( int i = 1; i <= N; i++ ){
        cin >> arr[i];
        pref[i] = pref[i-1] + arr[i];
    }

    for( int i = 1; i <= N; i++ ){
        best[i] = max( best[i], best[i-1] );
        dp[i] = 1 + dp[best[i]];
        lli currSum = 2 * pref[i] - pref[best[i]];
        int next = lower_bound(pref.begin() + 1, pref.begin() + N + 1, currSum ) - pref.begin();
        best[next] = max( best[next], i );
    }

    cout << dp[N] << endl;




    
    return 0;
}

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