Submission #1260560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260560		biank	Overtaking (IOI23_overtaking)	C++17	100 / 100	380 ms	45904 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
 
#define pb push_back
#define eb emplace_back
 
#define fst first
#define snd second
 
using namespace std;
 
using vi = vector<int>;
using ii = pair<int, int>;
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;

const int MAX_N = 1005;

ll e[MAX_N][MAX_N], dp[MAX_N][MAX_N];
ll s[MAX_N], w[MAX_N], t[MAX_N], x;
int n, m;

void init(int /*L*/, int N, vll T, vi W, int X, int M, vi S) {
    n = M, m = N, x = X;
    forn(i, n) s[i] = S[i];
    {
        int j = 0;
        forn(i, m) if (W[i] > X) {
            w[j] = W[i], t[j] = T[i];
            j++;
        }
        m = j;
    }
    vector<pll> v(m);
    forn(i, m) v[i] = {t[i], w[i]};
    forn(i, n) {
        sort(all(v));
        forn(j, m) {
            if (i > 0) v[j].fst += v[j].snd * (s[i] - s[i - 1]);
            if (j > 0) v[j].fst = max(v[j].fst, v[j - 1].fst);
            e[i][j] = v[j].fst;
        }
    }
    forn(j, m) dp[n - 1][j] = e[n - 1][j];
    dforn(i, n - 1) {
        dp[i][0] = e[i][0] + (s[n - 1] - s[i]) * x;
        forsn(j, 1, m) {
            int lo = i, hi = n;
            while (hi - lo > 1) {
                int mid = (lo + hi) / 2;
                if (e[mid][j - 1] >= e[i][j] + (s[mid] - s[i]) * x) {
                    hi = mid;
                } else {
                    lo = mid;
                }
            }
            if (hi == n) dp[i][j] = e[i][j] + (s[n - 1] - s[i]) * x;
            else dp[i][j] = dp[hi][j - 1];
        }
        forsn(j, 1, m) if (e[i][j] == e[i][j - 1]) dp[i][j] = min(dp[i][j], dp[i][j - 1]);
        dforn(j, m - 1) if (e[i][j] == e[i][j + 1]) dp[i][j] = min(dp[i][j], dp[i][j + 1]);
    }
}

ll arrival_time(ll Y) {
    int lo = -1, hi = m;
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        if (e[0][mid] < Y) lo = mid;
        else hi = mid;
    }
    if (lo == -1) return Y + s[n - 1] * x;
    int curr = lo;
    lo = -1, hi = n;
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        if (e[mid][curr] >= Y + s[mid] * x) {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    if (hi == n) return Y + s[n - 1] * x;
    return dp[hi][curr];
}

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