Submission #1246470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246470		colossal_pepe	Overtaking (IOI23_overtaking)	C++20	39 / 100	3593 ms	416 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Car {
    ll t, w;
    Car(ll _t, ll _w) : t(_t), w(_w) { }
    Car() { }
};

ll l, x;
int n, m;
vector<ll> s;
vector<Car> cars;

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
    l = L, x = X;
    n = N, m = M;
    cars.resize(n);
    for (int i = 0; i < n; i++) {
        cars[i] = Car(T[i], W[i]);
    }
    s.assign(S.begin(), S.end());
    return;
}

ll arrival_time(ll Y) {
    // cerr << "BRUH " << Y << ' ' << x << ' ' << s[1] << endl;
    ll start = Y, arrive;
    vector<Car> cars_cur = cars;
    vector<Car> cars_nxt(n);
    for (int i = 1; i < m; i++) {
        sort(cars_cur.begin(), cars_cur.end(), [](Car c1, Car c2) {
            return make_pair(c1.t, c1.w) < make_pair(c2.t, c2.w);
        });
        arrive = start + x * (s[i] - s[i - 1]);
        for (int j = 0; j < n; j++) {
            cars_nxt[j] = cars_cur[j];
            cars_nxt[j].t = cars_cur[j].t + cars_nxt[j].w * (s[i] - s[i - 1]);
            if (j) cars_nxt[j].t = max(cars_nxt[j].t, cars_nxt[j - 1].t);
            if (cars_cur[j].t < start) arrive = max(arrive, cars_nxt[j].t);
        }
        swap(cars_cur, cars_nxt);
        // cerr << "STUF" << endl;
        // for (int j = 0; j < n; j++) {
        //     cerr << cars_cur[j].t << ' ';
        // }
        // cerr << arrive << ' ' << "STUF" << endl;
        start = arrive;
    }
    return start;
}

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