Submission #769945

#	Time	Username	Problem	Language	Result	Execution time	Memory
769945		Jomnoi	Bigger segments (IZhO19_segments)	C++17	37 / 100	4 ms	408 KiB

segments

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

const int MAX_N = 3005;
const long long INF = 1e18 + 7;

long long A[MAX_N], dp1[MAX_N], dp2[MAX_N];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int N;
    cin >> N;

    for (int i = 1; i <= N; i++) cin >> A[i];

    for (int i = 1; i <= N; i++) dp1[i] = dp2[i] = INF;
    for (int i = 1; i <= N; i++) {
        long long sum = 0;
        for (int j = i; j >= 1; j--) {
            sum += A[j];
            if (dp1[j - 1] <= sum) {
                dp1[i] = sum;
                dp2[i] = dp2[j - 1] + 1;
                break;
            }
        }
    }
    cout << dp2[N];
    return 0;
}

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