Submission #1057917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057917		mc061	Overtaking (IOI23_overtaking)	C++17	0 / 100	2 ms	4700 KiB

overtaking

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

const int N = 5+3;
const int M = 5+3;

int n, m;

int reserve_speed;

vector<pair<int64_t, int>> init_by_arrival;
int speed[N];
int stations[M]={};

void init(int l, int n_, std::vector<long long> t, std::vector<int> w, int x, int m_, std::vector<int> s) {
    n = n_;
    m = m_;
    reserve_speed = x;
    for (int i = 0; i < n; ++i) {
        speed[i] = w[i];
        init_by_arrival.emplace_back(t[i], i);
    }
    for (int i = 0; i < m; ++i) {
        stations[i] = s[i];
    }
    speed[n] = reserve_speed;
}

long long arrival_time(long long Y) {
    vector<pair<int64_t, int>> by_arrival = init_by_arrival;
    vector<pair<int64_t, int>> swp;
    by_arrival.push_back({Y, n});
    for (int st = 0; st+1 < m; ++st) {
        int64_t mx_prev = -3e18;
        sort(by_arrival.begin(), by_arrival.end(), [&] (auto& a, auto& b) {
            if (b.first == a.first) return speed[b.second] > speed[a.second];
            return a.first < b.first;
        });
        int64_t d = stations[st+1]-stations[st];
        for (int i = 0; i < n+1; ++i) {
            swp.push_back({max(mx_prev, by_arrival[i].first+d*speed[by_arrival[i].second]), by_arrival[i].second});
            mx_prev = max(mx_prev, by_arrival[i].first+d*speed[by_arrival[i].second]);
        }
        by_arrival.swap(swp);
        swp.clear();
    }
    for (auto& x : by_arrival) {
        if (x.second == n) return x.first;
    }
    return -1;
}

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