oj.uz

Submission #527768

# Submission time Handle Problem Language Result Execution time Memory
527768 2022-02-18T08:58:20 Z KoD Cigle (COI21_cigle) C++17
0 / 100
 4 ms 3288 KB 
#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] = 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 216 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 216 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3288 KB Output is correct
2 Incorrect 4 ms 3288 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 216 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 216 KB Output isn't correct
4 Halted 0 ms 0 KB -