Submission #527769

#	Time	Username	Problem	Language	Result	Execution time	Memory
527769		KoD	Cigle (COI21_cigle)	C++17	100 / 100	513 ms	294728 KiB

cigle

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

constexpr int M = 5000;
constexpr int inf = (1ll << 30) - 1;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<int> D(N + 1);
    for (int i = 0; i < N; ++i) {
        std::cin >> D[i + 1];
        D[i + 1] += D[i];
    }
    vector score(N + 1, vector(N + 1, 0));
    for (int m = 0; m <= N; ++m) {
        for (int l = m - 1, r = m, s = 0; l >= 0; --l) {
            while (r <= N and D[m] - D[l] > D[r] - D[m]) {
                r += 1;
            }
            if (r <= N) {
                score[m][l] = s;
                s += (D[m] - D[l] == D[r] - D[m]);
            }
        }
        for (int r = m + 1, l = m, s = 0; r <= N; ++r) {
            while (l >= 0 and D[r] - D[m] > D[m] - D[l]) {
                l -= 1;
            }
            if (l >= 0) {
                score[m][r] = s;
                s += (D[m] - D[l] == D[r] - D[m]);
            }
        }
    }
    vector dp(N + 1, vector(N + 1, -inf));
    vector max(N + 1, vector(N + 1, -inf));
    for (int j = 1; j <= N; ++j) {
        dp[0][j] = 0;
    } 
    for (int i = 0; i <= N; ++i) {
        int l = i, r = i;
        for (int j = i; j <= N; ++j) {
            
            if (i > 0) {
                max[i][j] = std::max(max[i][j], max[i - 1][j]);
            }
            
            // l, i -> i, j
            // D[i] - D[j] <= D[i] - D[l]
            // dp[l][i] + score[i][j]
            while (l >= 0 and D[j] - D[i] > D[i] - D[l]) {
                l -= 1;
            }
            if (l >= 0) {
                dp[i][j] = std::max(dp[i][j], max[l][i] + score[i][j]);
            }

            if (j > 0) {
                dp[i][j] = std::max(dp[i][j], dp[i][j - 1]);
            }

            max[i][j] = std::max(max[i][j], dp[i][j]);

            // i, j -> j, r
            // D[j] - D[i] <= D[r] - D[j]
            // dp[i][j] + score[j][i]
            while (r <= N and D[j] - D[i] > D[r] - D[j]) {
                r += 1;
            }
            if (r <= N) {
                dp[j][r] = std::max(dp[j][r], dp[i][j] + score[j][i]);
            }

        }
    }
    int ans = 0;
    for (const auto& v : dp) {
        for (const auto& x : v) {
            ans = std::max(ans, x);
        }
    }
    std::cout << ans << '\n';
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 52 / 52