Submission #1072040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072040		zsombor	Overtaking (IOI23_overtaking)	C++17	65 / 100	3524 ms	58192 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));

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());
}

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);
}

ll arrival_time(ll Y) {
    ll T = Y;
    for (int j = 0; j < m - 1; j++) {
        pair<pair<ll, ll>, ll> p = {{T, x}, n};
        int i = upper_bound(a[j].begin(), a[j].end(), p) - a[j].begin();
        p = a[j][i - 1];
        T += x * (s[j + 1] - s[j]);
        T = max(T, v[j + 1][p.second]);
    }
    return T;
}

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