제출 #997285

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997285		biank	추월 (IOI23_overtaking)	C++17	65 / 100	3555 ms	34644 KiB

overtaking

#include <bits/stdc++.h>

using namespace std;

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

using ll = long long;

const ll INF = 1e18;

vector<ll> times;
vector<int> s, w;
vector<vector<ll>> e, t;
vector<vector<pair<ll, ll>>> order;
int v, m, x;

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
    for (int i = 0; i < N; i++) {
        if (W[i] <= X) continue;
        w.push_back(W[i]);
        times.push_back(T[i]);
    }
    m = M;
    x = X;
    s = S;
    N = sz(w);
    e.assign(M, vector<ll>(N));
    t.assign(M, vector<ll>(N));
    for (int i = 0; i < N; i++) {
        t[0][i] = times[i];
    }
    for (int i = 1; i < M; i++) {
        for (int j = 0; j < N; j++) {
            e[i][j] = t[i - 1][j] + 1LL * w[j] * (s[i] - s[i - 1]);
        }
        vector<int> p(N);
        iota(all(p), 0);
        sort(all(p), [&](int a, int b) {
            return t[i - 1][a] < t[i - 1][b];
        });
        ll prev = -1;
        order.push_back({{-1, -1}});
        for (int j = 0; j < N; j++) {
            int k = j;
            while (k + 1 < N && t[i - 1][p[k]] == t[i - 1][p[k + 1]]) {
                t[i][p[k]] = max(e[i][p[k]], prev);
                k++;
            }
            t[i][p[k]] = max(e[i][p[k]], prev);
            k = j;
            while (k + 1 < N && t[i - 1][p[k]] == t[i - 1][p[k + 1]]) {
                prev = max(prev, e[i][p[k]]);
                k++;
            }
            prev = max(prev, e[i][p[k]]);
            order.back().emplace_back(t[i - 1][p[k]], prev);
            j = k;
        }
    }
}

ll arrival_time(ll Y) {
    vector<ll> reserveT(m);
    vector<ll> reserveE(m);
    reserveT[0] = Y;
    for (int i = 1; i < m; i++) {
        reserveE[i] = reserveT[i - 1] + 1LL * x * (s[i] - s[i - 1]);
        auto it = lower_bound(all(order[i - 1]), pair<ll, ll>{reserveT[i - 1], -1});
        --it;
        reserveT[i] = max(reserveE[i], it->second);
    }
    return reserveT[m - 1];
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 26 / 26
• Subtask 5: 0 / 35