Submission #1210170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210170		thangdz2k7	Overtaking (IOI23_overtaking)	C++20	10 / 100	1 ms	328 KiB

overtaking

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

using namespace std;
using ll = long long;

const int MAX = 1e3;

int n, m, x;
long long timer[MAX][MAX], ans[MAX][MAX];
pair <long long, int> buses[MAX];
vector <int> s;

void init(int L, int N, vector <ll> T, vector <int> W, int X, int M, vector <int> S){
    n = 0, m = M, x = X;
    s = S;
    for (int i = 0; i < N; ++ i) if (W[i] > X)
        buses[n ++] = make_pair(T[i], W[i]);

    if (n == 0) return;

    sort(buses, buses + n);
    for (int i = 0; i < n; ++ i)
        timer[0][i] = buses[i].first;

    for (int i = 1; i < m; ++ i){
        for (int j = 0; j < n; ++ j){
            buses[j].first += 1ll * (S[i] - S[i - 1]) * buses[j].second;
            if (j) buses[j].first = max(buses[j].first, buses[j - 1].first);
        }

        sort(buses, buses + n);
        for (int j = 0; j < n; ++ j)
            timer[i][j] = buses[j].first;
    }

    for (int i = 0; i < n; ++ i)
        ans[m - 1][i] = timer[m - 1][i];

    for (int i = m - 2; i >= 0; -- i){
        ans[i][0] = timer[i][0] + 1ll * (s[m - 1] - s[i]) * x;
        for (int j = 1; j < n; ++ j){
            if (timer[i][j] == timer[i][j - 1]){
                ans[i][j] = ans[i][j - 1];
                continue;
            }

            long long tmp = timer[i][j] + 1ll * (s[m - 1] - s[i]) * x;
            if (tmp >= timer[m - 1][j - 1]){
                ans[i][j] = tmp;
                continue;
            }

            int low = i + 1, high = m - 1;
            while (low < high){
                int mid = low + high >> 1;
                long long tmp = timer[i][j] + 1ll * (s[mid] - s[i]) * x;
                if (tmp < timer[mid][j - 1]) high = mid;
                else low = mid + 1;
            }

            ans[i][j] = ans[low][j - 1];
        }
    }
}

long long arrival_time(long long Y){
    long long tmp = Y + 1ll * s[m - 1] * x;
    if (n == 0 || Y <= timer[0][0])
        return tmp;

    int low = 1, high = n;
    while (low < high){
        int mid = low + high >> 1;
        if (timer[0][mid] >= Y) high = mid;
        else low = mid + 1;
    }

    int i = low - 1;
    if (timer[m - 1][i] <= tmp) return tmp;

    low = 1, high = m - 1;
    while (low < high){
        int mid = low + high >> 1;
        long long tmp = Y + 1ll * s[mid] * x;
        if (tmp < timer[mid][i]) high = mid;
        else low = mid + 1;
    }

    return ans[low][i];
}

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