Submission #981056

#	Time	Username	Problem	Language	Result	Execution time	Memory
981056		vjudge1	Overtaking (IOI23_overtaking)	C++17	0 / 100	1 ms	604 KiB

overtaking

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

const ll MAXN = 1E3+16;
ll l, n, x, m;
vll t[MAXN], e[MAXN];
vll prefM[MAXN];
vll ist[MAXN], is[MAXN];
vi w, s;
// bus i moves 1 km in w[i] s/km

void init (int L, int N, vll T, vi W, int X, int M, vi S) {
    l = L; n = N; x = X; m = M;
    t[0] = T;
    w = W; s = S;
    for (ll i = 1; i < m; i++) {
        ll dis = s[i]-s[i-1];
        e[i].assign(n, -15);
        for (ll j = 0; j < n; j++) {
            e[i][j] = t[i-1][j] + dis*w[j];
        }
        t[i].assign(n, -15);
        is[i].assign(n, -15);
        iota(is[i].begin(), is[i].end(), 0);
        sort(is[i].begin(), is[i].end(), [&](ll a, ll b) {
            return t[i-1][a] < t[i-1][b];
        });
        ist[i].assign(n, -15);
        for (ll j = 0; j < n; j++) {
            ist[i][j] = t[i-1][is[i][j]];
        }
        prefM[i].assign(n, -15);
        prefM[i][0] = e[i][is[i][0]];
        for (ll j = 1; j < n; j++) {
            prefM[i][j] = max(prefM[i][j-1], e[i][is[i][j]]);
        }
        for (ll j = 0; j < n; j++) {
            ll idx = upper_bound(is[i].begin(), is[i].end(), t[i-1][j]-1, [&](ll a, ll b) {
                return t[i-1][a] < t[i-1][b];
            }) - is[i].begin()-1;
            if (idx < 0) t[i][j] = e[i][j];
            else t[i][j] = max(e[i][j], prefM[i][idx]);
        }
    }
}

ll arrival_time (ll y) {
    for (ll i = 1; i < m; i++) {
        ll dis = s[i]-s[i-1];
        ll ey = y + dis*x;
        ll idx = upper_bound(ist[i].begin(), ist[i].end(), y-1) - ist[i].begin()-1;
        if (idx < 0) y = ey;
        else y = max(ey, prefM[i][idx]);
    }
    return y;
}

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