Submission #847911

#	Time	Username	Problem	Language	Result	Execution time	Memory
847911		Rifal	Overtaking (IOI23_overtaking)	C++17	39 / 100	3547 ms	600 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
vector<long long> sta;
vector<pair<long long, long long>> bus;
int n, 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;
    for(int i = 0; i < M; i++) sta.push_back(S[i]);
    for(int i = 0; i < N; i++) bus.push_back({T[i],W[i]});
    bus.push_back({-1,X});
}

long long arrival_time(long long Y)
{
    int siz = bus.size();
    bus[siz-1].first = Y;
    long long cur[siz];
    for(int i = 0; i < siz; i++) {
        cur[i] = bus[i].first;
    }
    for(int i = 1; i < m; i++) {
        priority_queue<pair<pair<long long, long long>,int>, vector<pair<pair<long long,long long>,int>>, greater<pair<pair<long long, long long>,int>>> pq;
        pair<long long, long long> mx = {-1,-1};
        for(int j = 0; j < siz; j++) {
        //    cout << cur[j] << ' ' << bus[j].second << ' ' << sta[i] << ' ' << sta[i-1] << ' ' << j << endl;
            pq.push({{cur[j],cur[j] + bus[j].second * (sta[i]-sta[i-1])},j});
        }
        while(!pq.empty()) {
            pair<pair<long long, long long>,int> tp = pq.top(); pq.pop();
            if(mx.first < tp.first.second) {
                mx.first = tp.first.second;
                mx.second = tp.first.first;
            }
            if(mx.second == tp.first.first) {
                cur[tp.second] = tp.first.second;
            }
            else {
                cur[tp.second] = mx.first;
            }
        }
    }
    return cur[siz-1];
}
/*
6 4 10 4 2
20 10 40 0
5 20 20 30
0 1 3 6
0
50*/

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