Submission #636091

#	Time	Username	Problem	Language	Result	Execution time	Memory
636091		eecs	Cigle (COI21_cigle)	C++17	100 / 100	297 ms	98672 KiB

cigle

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

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vector<int> d(n);
    for (int &x : d) {
        cin >> x;
    }
    vector<vector<int>> f(n, vector<int>(n));
    for (int i = 0; i < n - 1; i++) {
        vector<int> num(n);
        int l = i, r = i + 1, s = 0, cnt = 0;
        while (~l || r < n) {
            if (r == n || s <= 0 && l >= 0) s += d[l--];
            else s -= d[r++];
            if (!s) cnt++;
            if (~l) num[l] = cnt;
            if (r < n) num[r] = cnt;
        }
        vector<int> pre(i + 1);
        for (int j = 0; j <= i; j++) {
            pre[j] = max(j ? pre[j - 1] : 0, f[j][i]);
        }
        for (int k = i + 1, j = i, t = 0; k < n; k++) {
            for (; ~j && num[j] <= num[k]; j--) {
                t = max(t, f[j][i] + num[j]);
            }
            f[i + 1][k] = max(t, ~j ? pre[j] + num[k] : 0);
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, f[i][n - 1]);
    }
    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

cigle.cpp: In function 'int main()':
cigle.cpp:17:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   17 |             if (r == n || s <= 0 && l >= 0) s += d[l--];
      |                           ~~~~~~~^~~~~~~~~

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