Submission #997934

#	Time	Username	Problem	Language	Result	Execution time	Memory
997934		arbuzick	Cigle (COI21_cigle)	C++17	100 / 100	403 ms	97464 KiB

cigle

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 5e3 + 5;

int dp[maxn][maxn];

void solve() {
    int n;
    cin >> n;
    vector<int> d(n);
    for (int i = 0; i < n; ++i) {
        cin >> d[i];
    }
    for (int r = 1; r < n; ++r) {
        vector<int> pr_sum_left = {0}, pr_sum_right = {0};
        vector<int> pr_max(r + 1);
        for (int i = 0; i < r; ++i) {
            pr_max[i + 1] = max(pr_max[i], dp[i][r]);
        }
        for (int i = r - 1; i >= 0; --i) {
            pr_sum_left.push_back(pr_sum_left.back() + d[i]);
        }
        for (int i = r; i < n; ++i) {
            pr_sum_right.push_back(pr_sum_right.back() + d[i]);
        }
        int ans_nw = pr_max[r], cnt_nw = 0;
        for (int r2 = r + 1; r2 <= n; ++r2) {
            dp[r][r2] = ans_nw;
            int pos = lower_bound(pr_sum_left.begin(), pr_sum_left.end(), pr_sum_right[r2 - r]) - pr_sum_left.begin();
            if (pos != pr_sum_left.size() && pr_sum_left[pos] == pr_sum_right[r2 - r]) {
                int l = r - pos;
                if (l != 0) {
                    cnt_nw++;
                    ans_nw = max(ans_nw, pr_max[l] + cnt_nw);
                }
            }
        }
    }
    int ans = 0;
    for (int l = 0; l < n; ++l) {
        for (int r = l + 1; r <= n; ++r) {
            ans = max(ans, dp[l][r]);
        }
    }
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

cigle.cpp: In function 'void solve()':
cigle.cpp:32:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             if (pos != pr_sum_left.size() && pr_sum_left[pos] == pr_sum_right[r2 - r]) {
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~

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