Submission #1211201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211201		omsincoconut	Overtaking (IOI23_overtaking)	C++17	65 / 100	3593 ms	24648 KiB

overtaking

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

int L, N;
vector<ll> T;
vector<int> W;
int X, M;
vector<int> S;

vector<vector<pll>> precom;

void init(int _L, int _N, vector<ll> _T, vector<int> _W, int _X, int _M, vector<int> _S) {
    L = _L; N = _N; T = _T; W = _W; X = _X; M = _M; S = _S;

    vector<vector<ll>> dp(M, vector<ll>(N));
    dp[0] = T;

    for (int i = 1; i < M; i++) {
        vector<array<ll, 3>> tmp(N);
        for (int j = 0; j < N; j++) tmp[j] = {dp[i-1][j], dp[i-1][j] + (ll)W[j]*(S[i]-S[i-1]), j};
        sort(tmp.begin(), tmp.end());

        vector<pll> compute(N);

        ll mxt = 0;
        for (int j = 0; j < N; j++) {
            mxt = max(mxt, tmp[j][1]);
            dp[i][tmp[j][2]] = mxt;

            compute[j] = make_pair(tmp[j][0], mxt);
        }
        precom.push_back(compute);
    }
}

ll arrival_time(ll Y) {
    ll cur = Y;
    for (int i = 0; i < M-1; i++) {
        int idx = lower_bound(precom[i].begin(), precom[i].end(), make_pair(cur-1, (ll)1e18)) - precom[i].begin() - 1;
        ll val = cur + (ll)X*(S[i+1]-S[i]);
        if (idx >= 0) val = max(val, precom[i][idx].second);
        cur = val;
    }

    return cur;
}

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