Submission #841457

#	Time	Username	Problem	Language	Result	Execution time	Memory
841457		model_code	Overtaking (IOI23_overtaking)	C++17	10 / 100	2 ms	340 KiB

overtaking

// correct/sol_na_st2.cpp

#include "overtaking.h"
#include <algorithm>
#include <numeric>
#include <iostream>
#include <cassert>

using namespace std;
using ll = long long;

int L, N, X, M;
vector<long long> T;
vector<int> W, S;

vector<long long> dp;
vector<int> ord;

void init(int L_, int N_, std::vector<long long> T_, std::vector<int> W_, int X_, int M_, std::vector<int> S_)
{
    L = L_;
    N = N_;
    T = T_;
    W = W_;
    X = X_;
    M = M_;
    S = S_;

    T.push_back(-1);
    dp.assign(N, 0);
    for (int i = 0; i < N; ++i)
    {
        dp[i] = T[i] + ll(W[i]) * ll(S[1] - S[0]);
    }
    ord.assign(N, 0);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) -> bool
         { return T[x] < T[y]; });

    for (int i = 1; i < N; ++i)
    {
        if (dp[ord[i - 1]] > dp[ord[i]])
        {
            dp[ord[i]] = dp[ord[i - 1]];
        }
    }

    return;
}

long long arrival_time(long long Y)
{
    int x = -1;
    for (int j = 10; j >= 0; j--)
    {
        int xx = x + (1 << j);
        if (xx < N && T[ord[xx]] < Y)
            x = xx;
    }
    ll base = Y + (ll)X * ll(S[1] - S[0]);
    if (x == -1)
        return base;

    return max(base, dp[ord[x]]);
}

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