Submission #168420

#	Time	Username	Problem	Language	Result	Execution time	Memory
168420		IldarKA	Bigger segments (IZhO19_segments)	C++14	37 / 100	86 ms	28024 KiB

segments

#include <bits/stdc++.h>

using namespace std;
int n;
long long a[3001];
int dp[3001][3001];
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        dp[1][i] = 1;
    }
    for(int i = 2; i <= n; i++){
        int po = i - 1;
        long long sum = 0;
        long long sum2 = 0;
        int mx = 0;
        for(int j = i; j <= n; j++){
            sum += a[j];
            while(po > 0 && sum2 + a[po] <= sum){
                sum2 += a[po];
                mx = max(dp[po][i - 1], mx);
                po--;
            }
            if(po < i - 1 && mx > 0){
                dp[i][j] = max(mx + 1, dp[i][j]);
            }
        }
    }
    int mx = 0;
    for(int i = 1; i <= n; i++){
        mx = max(dp[i][n], mx);
    }
    cout << mx;
}

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