Submission #1215499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215499		trimkus	Overtaking (IOI23_overtaking)	C++20	39 / 100	3589 ms	8336 KiB

overtaking

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

using namespace std;
using ll = long long;

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



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;
    M = _M;
    N = _N;
    T = _T;
    W = _W;
    X = _X;
    S = _S;
    W.push_back(X);
}

long long arrival_time(long long Y)
{
    vector<vector<ll>> exp(N + 1, vector<ll>(M));
    vector<int> ord(N + 1);
    iota(begin(ord), end(ord), 0);
    for (int i = 0; i < N; ++i) {
        exp[i][0] = T[i];
    }
    exp[N][0] = Y;
    for (int j = 1; j < M; ++j) {
        sort(begin(ord), end(ord), [&](int x, int y){
            if (exp[x][j - 1] != exp[y][j - 1]) return exp[x][j - 1] < exp[y][j - 1];
            return W[x] < W[y];
        });
        ll tim = -1;
        for (int it = 0; it <= N; ++it) {
            int i = ord[it];
            // cerr << W[i] << " ";
            exp[i][j] = exp[i][j - 1] + 1LL * W[i] * (S[j] - S[j - 1]);
            exp[i][j] = max(tim, exp[i][j]);
            tim = max(exp[i][j], tim);
        }
        // cerr << endl;
    }
    // cerr << Y << ":\n";
    // for (int j = 0; j < M; ++j) {
    //     for (int i = 0; i <= N; ++i) {
    //         cerr << exp[i][j] << " ";
    //     }
    //     cerr << "\n";
    // }
    // cerr << "\n";
    return exp[N][M - 1];
}

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