Submission #1188383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188383		MatteoArcari	Overtaking (IOI23_overtaking)	C++20	9 / 100	3 ms	328 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;

ll x, n, m, l;
vector<ll> w, t, s;
vector<vector<ll>> dp;

void init(int _l, int _n, vector<ll> _t, vi _w, int _x, int _m, vi _s) {
    n = _n; m = _m; x = _x; l = _l; t = _t;
    w = vector<ll>(_w.begin(), _w.end());
    s = vector<ll>(_s.begin(), _s.end());

    dp.resize(m, vector<ll>(n));
    dp[0] = t;

    vector<pair<ll, int>> srt(n);
    for (int i = 0; i < n; i++) {
        srt[i] = {dp[0][i], i};
    }

    sort(srt.begin(), srt.end(), [&](auto _i, auto _j){
        if (_i.first == _j.first) return w[_i.second] < w[_j.second];
        return _i.first < _j.first;
    });

    for (int j = 1; j < m; j++) {
        ll ma = 0;
        for (auto [tm, i]: srt) {
            ma = max(ma, dp[j - 1][i] + w[i] * (s[j] - s[j - 1]));
            dp[j][i] = ma;
        }

        for (int i = 0; i < n; i++) {
            srt[i] = {dp[j][i], i};
        }
        sort(srt.begin(), srt.end(), [&](auto _i, auto _j){
            if (_i.first == _j.first) return w[_i.second] < w[_j.second];
            return _i.first < _j.first;
        });
    } 

}

ll arrival_time(ll y) {
    priority_queue<pair<ll, int>> pq;
    ll time = y;
    ll ma = time;
    for (int i = 0; i < n; i++) {
        if (w[i] <= x) continue;
        if (t[i] >= y) continue;
        int j = 0;
        for (int k = 1 << 14; k; k >>= 1) {
            if (j + k < m && dp[j + k][i] < y + x * s[j + k]) {
                j += k;
            }
        }
        if (++j == m) continue;
        pq.push({-j, i});
    }

    for (int j = 1; j < m; j++) {
        time += x * (s[j] - s[j - 1]);
        while (!pq.empty()) {
            auto [_, i] = pq.top();
            if (dp[j][i] >= time) {
                pq.pop();
                time = dp[j][i];
            } else {
                break;
            }
        }
    }

    return time;
}

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