Submission #1211192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211192		omsincoconut	Overtaking (IOI23_overtaking)	C++17	39 / 100	3594 ms	416 KiB

overtaking

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

using namespace std;
typedef long long ll;

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

void init(int _L, int _N, vector<ll> _T, vector<int> _W, int _X, int _M, vector<int> _S) {
    L = _L; N = _N; T = _T; W = _W; X = _X; M = _M; S = _S;
}

ll arrival_time(ll Y) {
    vector<ll> dp = T;
    dp.push_back(Y);

    for (int i = 1; i < M; i++) {
        vector<array<ll, 3>> tmp(N+1);
        for (int j = 0; j < N; j++) tmp[j] = {dp[j], dp[j] + (ll)W[j]*(S[i]-S[i-1]), j};
        tmp[N] = {dp[N], dp[N] + (ll)X*(S[i]-S[i-1]), N};
        sort(tmp.begin(), tmp.end());

        ll mxt = 0;
        for (int j = 0; j <= N; j++) {
            mxt = max(mxt, tmp[j][1]);
            dp[tmp[j][2]] = mxt;
        }
    }

    return dp[N];
}

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