Submission #1072169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072169		zsombor	Overtaking (IOI23_overtaking)	C++17	19 / 100	37 ms	63776 KiB

overtaking

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

ll l, n, x, m;
vector<ll> t;
vector<ll> w(2e3, 0);
vector<ll> s(2e3, 0);
vector<vector<pair<pair<ll, ll>, ll> > > a(2e3);
vector<vector<ll> > v(2e3, vector<ll>(2e3, 0));
vector<vector<pair<ll, ll> > > u(2e3);
vector<vector<ll> > dp(2e3, vector<ll>(2e3, 0));

void solve(int j) {
    for (auto p: a[j - 1]) {
        ll T = p.first.first + p.first.second * (s[j] - s[j - 1]);
        a[j].push_back({{T, p.first.second}, p.second});
    }
    for (int i = 1; i <= n; i++) {
        a[j][i].first.first = max(a[j][i].first.first, a[j][i - 1].first.first);
        v[j][a[j][i].second] = a[j][i].first.first;
    }
    sort(a[j].begin(), a[j].end());
}

ll calc(int j, ll t) {
    pair<ll, ll> p = {t, -1};
    int lb = lower_bound(u[j].begin(), u[j].end(), p) - u[j].begin();
    if (!lb) return t + x * (s[m - 1] - s[j]);
    int i = u[j][lb - 1].second, l = j, r = m, k;
    while (r - l > 1) {
        k = (l + r) / 2;
        (v[k][i] < t + x * (s[k] - s[j]) ? l = k : r = k);
    }
    if (r == m) return t + x * (s[m - 1] - s[j]);
    return dp[r][i];
}

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
    l = L;
    n = N;
    x = X;
    m = M;
    t = T;
    for (int i = 0; i < n; i++) w[i] = W[i];
    for (int j = 0; j < m; j++) s[j] = S[j];
    for (int i = 0; i < n; i++) a[0].push_back({{t[i], w[i]}, ll(i)});
    a[0].push_back({{0, 0}, n + 1});
    a[0].push_back({{4e18, 0}, n + 1});
    sort(a[0].begin(), a[0].end());
    for (int j = 1; j < m; j++) solve(j);

    for (int j = 0; j < m; j++) {
        for (int i = 1; i <= n; i++) {
            if (a[j][i].first.second <= x) continue;
            u[j].push_back({a[j][i].first.first, a[j][i].second});
        }
    }

    for (int i = 0; i < n; i++) {
        dp[m - 1][i] = v[m - 1][i];
    }
    for (int j = m - 2; j >= 0; j--) {
        for (int i = 0; i < n; i++) {
            dp[j][i] = calc(j, v[j][i]);
        }
    }
}

ll arrival_time(ll Y) {
    return calc(0, Y);
}

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