제출 #467164

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
467164		theconfusedguy	Bigger segments (IZhO19_segments)	C++14	0 / 100	1 ms	204 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 main(){
    SPEED;

    int N; cin >> N;
    int arr[N+1];
    for( int i = 1; i <= N; i++ ) cin >> arr[i];
    vector<lli> dp(N+2, 0);
    vector<lli> prevMinimalSum(N+2, 0);

    dp[1] = 1;
    prevMinimalSum[1] = arr[1];

    for( int i = 2; i <= N; i++ ){
        lli currSum = 0;
        for( int j = i; j >= 1; j-- ){
            currSum += arr[j];
            if( currSum >= prevMinimalSum[j-1] && dp[i] < 1 + dp[j-1] ){
                dp[i] = 1 + dp[j-1];
                prevMinimalSum[i] = currSum;
            }
        }
    }

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

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