Submission #1122551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122551		AnhPham	Bikeparking (EGOI24_bikeparking)	C++20	25 / 100	389 ms	69456 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int     long long
#define sz(v)   (int)(v).size()
#define all(v)  (v).begin(), (v).end()

const   int     MOD = (int)1e9 + 7;
const   int     INF = (int)4e18 + 18;

void solve();

int32_t main() {
#define CODE ""
    if (fopen(CODE".inp", "r"))
        freopen(CODE".inp", "r", stdin), freopen(CODE".out", "w", stdout);

    cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(false);
    int testcases = 1;

#define multitest 0
    if (multitest) { cin >> testcases; } for (; testcases--;) { solve(); }
}

/** [Pham Hung Anh - 12I - Tran Hung Dao High School for Gifted Student] **/
/**                            The Last Dance                            **/

const int mxN = 3e5 + 5;

int N;
int X[mxN], Y[mxN];

namespace sub2 {
    bool check_condition() {
        return (*min_element(X, X + N) == *max_element(X, X + N) && *min_element(Y, Y + N) == *max_element(Y, Y + N));
    }

    void solve() {
        cout << max(0ll, X[0] * (N - 2)) << '\n';
    }
}

namespace sub14 {
    int dp[202][202 * 202];

    void solve() {
        int sum_diff = 0;
        for (int i = 0; i < N; ++i)
            sum_diff += X[i] - Y[i];

        for (int i = N - 1; i >= 0; --i) {
            if (X[i] <= sum_diff) {
                sum_diff -= X[i];
                X[i] = 0;
            } else {
                X[i] -= sum_diff;
                break;
            }
        }

        for (int i = 0; i <= N; ++i)
            for (int j = 0; j < 200 * 200; ++j)
                dp[i][j] = -INF;

        dp[0][0] = 0;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < 200 * 200; ++j)
                for (int k = 0; k <= min(X[i] + j, Y[i]); ++k)
                    dp[i + 1][X[i] + j - k] = max(dp[i + 1][X[i] + j - k], dp[i][j] + min(j, k));

        int ans = -INF;
        for (int i = 0; i < 200 * 200; ++i)
                ans = max(ans, dp[N][i] - i);

        cout << ans << '\n';
    }
}

void solve() {
    cin >> N;

    for (int i = 0; i < N; ++i)
        cin >> X[i];

    for (int i = 0; i < N; ++i)
        cin >> Y[i];


    if (sub2 :: check_condition())
        sub2 :: solve();
    else
        sub14 :: solve();
}

Compilation message (stderr)

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

• Subtask 1: 16 / 16
• Subtask 2: 9 / 9
• Subtask 3: 0 / 19
• Subtask 4: 0 / 24
• Subtask 5: 0 / 32