Submission #1217999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217999		qwusha	Closing Time (IOI23_closing)	C++17	21 / 100	1096 ms	9796 KiB

closing

#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
ll inf = 1e18;

ll n, x, y;



int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    x = X;
    y = Y;
    vector<ll> dx(n), dy(n);
    dx[x] = 0;
    for (ll i = x - 1; i >= 0; i--) {
        dx[i] = dx[i + 1] + W[i];
    }
    for (ll i = x + 1; i < n; i++) {
        dx[i] = dx[i - 1] + W[i - 1];
    }
    dy[y] = 0;
    for (ll i = y - 1; i >= 0; i--) {
        dy[i] = dy[i + 1] + W[i];
    }
    for (ll i = y + 1; i < n; i++) {
        dy[i] = dy[i - 1] + W[i - 1];
    }
    int res = 0;
    for (ll rx = x; rx < n; rx++) {
        for (ll ly = y; ly >= 0; ly--) {
            vector<ll> d(n, -1);
            ll cur = 0;
            ll k = K;
            int cnt = 0;
            for (ll i = x; i <= rx; i++) {
                d[i] = max(d[i], dx[i]);
            }
            for (ll i = y; i >= ly; i--) {
                d[i] = max(d[i], dy[i]);
            }
            for (int i = 0; i < n; i++) {
                if (d[i] != -1) {
                    cur += d[i];
                    if (d[i] >= dy[i] && (i > y || (ly <= i && i <= y)))
                        cnt++;
                    if (d[i] >= dx[i] && (i < x || (x <= i && i <= rx)))
                        cnt++;
                }
            }
            if (cur > k) {
                continue;
            }
            k -= cur;
            ll lx = min(x - 1, ly - 1);
            ll ry = max(y + 1, rx + 1);
            while (lx >= 0 && ry < n) {
                if (dx[lx] < dy[ry]) {
                    if (k >= dx[lx]) {
                        cnt++;
                        k -= dx[lx];
                    }
                    lx--;
                } else {
                    if (k >= dy[ry]) {
                        cnt++;
                        k -= dy[ry];
                    }
                    ry++;
                }
            }
            while (lx >= 0) {
                if (k >= dx[lx]) {
                    cnt++;
                    k -= dx[lx];
                }
                lx--;
            }
            while (ry < n) {
                if (k >= dy[ry]) {
                    cnt++;
                    k -= dy[ry];
                }
                ry++;
            }
            res = max(res, cnt);
        }
    }
    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17