Submission #1204830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204830		ofoz	Bigger segments (IZhO19_segments)	C++17	27 / 100	1600 ms	141384 KiB

segments

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#define int long long
#define pi pair<int, int>
using namespace std;
const long long INF = INT64_MAX;
int getPrfx(int l, int r, const vector<int>& prfx) {
    int left = (l == 0) ? 0 : prfx[l - 1];
    int right = prfx[r];
    return right - left;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    vector<int> prfx(n + 1);
    prfx[0] = -1;
    prfx[1] = a[1];
    for (int i = 2; i <= n; ++i) {
        prfx[i] = prfx[i - 1] + a[i];
    }


    vector<vector<pair<int, int>>> dp(n + 1, vector<pair<int, int>>(n + 1, {INF, INF}));
    dp[0][0] = {0, 0};

    int cur = 0;
    for (int i = 1; i <= n; ++i) {
        cur += a[i];
        dp[i][1] = {0, cur};
    }

    for (int i = 1; i <= n; ++i) {
        for (int s = 2; s <= i; ++s) {
            dp[i][s] = dp[i - 1][s];
            if (dp[i][s].first != INT64_MAX) dp[i][s].second += a[i];

            for (int j = 1; j < i; ++j) {
                int curSeg = getPrfx(j + 1, i, prfx);
                if (dp[j][s - 1].second <= curSeg) {
                    pair<int, int> candidate = {dp[j][s - 1].second, curSeg};

                    if (make_pair(candidate.second, candidate.first) < make_pair(dp[i][s].second, dp[i][s].first)) {
                        dp[i][s] = candidate;
                    }
                }
            }
        }
    }

    for (int seg = n; seg >= 1; --seg) {
        if (dp[n][seg].first != INF) {
            cout << seg << "\n";
            return 0;
        }
    }

    cout << 1 << "\n";
    return 0;
}

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