Submission #846597

#	Time	Username	Problem	Language	Result	Execution time	Memory
846597		trnthienphc2003	Cigle (COI21_cigle)	C++17	100 / 100	218 ms	67432 KiB

cigle

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define fore(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define fort(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define fordt(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define forde(i, a, b) for (int i = (a), _b = (b); i > _b; --i)
#define trav(a, x) for (auto& a : x)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

using namespace std;
using namespace __gnu_pbds;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef int64_t i64;
typedef pair<int,int> _ii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
constexpr int maxn=2e5+7;
constexpr i64 oo=1e9+7;
int n, a[5007], dp[5007][5007];

void solve() {
    cin >> n;
    fort(i, 1, n) cin >> a[i];

    fort(mid, 1, n) {

        fore(i, 1, mid)
            maxi(dp[i][mid - 1], dp[i - 1][mid - 1]);

        int r = mid, l = mid - 1, sum_up = a[r], sum_down = a[l], cnt = 0;
        while(r < n || l > 1) {
            if(r >= n) {
                sum_down += a[--l];
                maxi(dp[mid][r], dp[l][mid - 1] + cnt);
            }

            else if(l <= 1) {
                sum_up += a[++r];
                // maxi(dp[mid][r], dp[l][mid - 1] + cnt);
                maxi(dp[mid][r], dp[mid][r - 1]);
            }

            else {
                if(sum_up >= sum_down) {
                    sum_down += a[--l];
                }

                else {
                    sum_up += a[++r];
                    maxi(dp[mid][r], dp[mid][r - 1]);
                }

                // else {
                //     maxi(dp[mid][r], dp[l][mid - 1] + cnt);
                //     maxi(dp[mid][r + 1], dp[mid][r]);

                //     sum_up += a[++r];
                //     sum_down += a[--l];
                //     ++cnt;
                //     maxi(dp[mid][r], dp[l][mid - 1] + cnt); 
                // }
            }

            if(r - mid >= 1 && mid - l >= 2 && sum_down - a[l] == sum_up - a[r]) ++cnt;
            maxi(dp[mid][r], dp[l][mid - 1] + cnt);
        }

        if(l > 1) maxi(dp[mid][r], dp[l - 1][mid - 1] + cnt);
    }

    int ans = 0;
    fort(i, 1, n) maxi(ans, dp[i][n]);
    cout << ans << '\n';
}

#define NAME "test."
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    if(fopen(NAME"inp", "r")) {
        freopen(NAME"inp", "r", stdin);
        freopen(NAME"out", "w", stdout);
    }

    int t=1;
    while(t--) solve();
}

Compilation message (stderr)

cigle.cpp: In function 'int main()':
cigle.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(NAME"inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
cigle.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(NAME"out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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