Submission #1037831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037831		fv3	Closing Time (IOI23_closing)	C++17	21 / 100	1075 ms	10440 KiB

closing

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

using namespace std;
typedef long long ll;

const ll INF = 1ll << 60ll;

int max_score(int N, int X, int Y, ll K,
              vector<int> U, vector<int> V, vector<int> W)
{
    // Subtask 4:
    // Find optimal distance X should move to the right
    // O(N²)

    int best = 0;
    for (int r = X; r < N; r++)
    {
        vector<ll> closingTime(N);

        int res = 0;
        ll k_sum = 0;

        for (int i = X + 1; i <= r; i++)
        {
            closingTime[i] = closingTime[i-1] + W[i-1];
            k_sum += closingTime[i];
            res++;
        }
        if (k_sum > K)
            break;

        for (int l = Y; l >= 0; l--)
        {
            int score = res;
            ll sum = k_sum;

            vector<ll> ct = closingTime;

            best = max(best, res);
            vector<ll> dist(N);
            for (int i = Y - 1; i >= l; i--)
            {
                dist[i] = dist[i+1] + W[i];
                sum += max(0ll, dist[i] - ct[i]);
                ct[i] = max(ct[i], dist[i+1] + W[i]);
                score++;
            }
            if (sum > K)
                break;

            priority_queue<pair<ll, int>> q;
            q.push({0, X});
            q.push({0, Y});

            dist[X] = 0;
            dist[Y] = 0;

            while (!q.empty())
            {
                int s = q.top().second;

                if (sum - q.top().first > K)
                    break;
                sum -= q.top().first;
                score++;
                q.pop();

                if (s <= X && s)
                {
                    // Go left as X
                    dist[s-1] = dist[s] + W[s-1];
                    q.push({-max(0ll, dist[s-1] - ct[s-1]), s-1});
                }
                else if (s >= Y && s < N - 1)
                {
                    // Go right as Y
                    dist[s+1] = dist[s] + W[s];
                    q.push({-max(0ll, dist[s+1] - ct[s+1]), s+1});
                }
            }

            //cerr << ": " << r << " " << l << " = " << score << " (" << sum << ")\n";
            best = max(best, score);
        }
    }

    return best;
}

• 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