제출 #1010676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1010676		mdn2002	추월 (IOI23_overtaking)	C++17	39 / 100	3527 ms	31836 KiB

overtaking

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

int l, n, x, m;
vector<int> s;
vector<pair<long long, int>> buses;
vector<vector<pair<long long, int>>> times;
vector<vector<pair<long long, long long>>> max_times;
long long arrival_time(long long time) {
    long long ans = time;
    for (int i = 1; i < m; i ++) {
        long long past_time = ans, speed = x, delta_time = s[i] - s[i - 1], time = past_time + speed * delta_time;
        for (auto [x, y] : max_times[i]) {
            if (x < past_time) time = max(time, y);
        }
        ans = time;
    }
    return ans;
}

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, x = X, m = M, s = S;
    for (int i = 0; i < N; i ++) {
        if (W[i] < X) continue;
        buses.push_back({T[i], W[i]});
    }
    n = buses.size();
    times.push_back(buses);

    vector<pair<long long, long long>> bb;
    max_times.push_back(bb);
    for (int i = 1; i < m; i ++) {
        sort(times[i - 1].begin(), times[i - 1].end());
        long long max_time = 0, delta_time = S[i] - S[i - 1];
        vector<pair<long long, int>> a;
        vector<pair<long long, long long>> b;

        for (int j = 0; j < n; j ++) {
            long long past_time = times[i - 1][j].first, speed = times[i - 1][j].second;
            long long time = past_time + speed * delta_time;
            max_time = max(max_time, time);
            a.push_back({max_time, speed});
            b.push_back({past_time, max_time});
        }
        times.push_back(a);
        max_times.push_back(b);
    }
}

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