Submission #1225355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225355		mariaclara	Closing Time (IOI23_closing)	C++20	35 / 100	1093 ms	14660 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef vector<int> vi;
typedef vector<ll> vl;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define mk make_pair
#define fr first
#define sc second

int max_score(int N, int X, int Y, ll K, vi U, vi V, vi W) {
    vl pref(N);
    
    for(int i = 1; i < N; i++)
        pref[i] = pref[i-1] + W[i-1];

    vl distX(N), distY(N);
    set<pli> cam, twice;

    for(int i = 0; i < N; i++) {
        distX[i] = abs(pref[i] - pref[X]);
        distY[i] = abs(pref[i] - pref[Y]);
        if(X <= i and i <= Y) cam.insert({min(distX[i], distY[i]), i});
    }

    vl dp(2*N+1, 1e18+1);
    dp[0] = 0;
    
    ll at_val = 0;
    while(!cam.empty()) {
        auto [D, ind] = *cam.begin();
        cam.erase(cam.begin());
        twice.insert({distX[Y] - 2*D, ind});

        at_val += D;
        dp[Y-X+1 - sz(cam)] = at_val;
    }

    while(!twice.empty()) {
        auto [D, ind] = *twice.begin();
        twice.erase(twice.begin());

        at_val += D;
        dp[2*(Y-X+1) - sz(twice)] = at_val;
    }

    for(int i = 0; i < N; i++) {
        if(X <= i and i <= Y) continue;

        int mi = min(distX[i], distY[i]), ma = max(distX[i], distY[i]);

        for(int qtd = 2*N; qtd > 0; qtd--)
            dp[qtd] = min({dp[qtd], dp[qtd-1] + mi, dp[qtd-2] + ma});
    }

    for(int qtd = 2*N; qtd > 0; qtd--)
        if(dp[qtd] <= K) return qtd;

    return 0;
}

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