Submission #1043545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043545		vnm06	Overtaking (IOI23_overtaking)	C++17	65 / 100	3570 ms	44444 KiB

overtaking

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

long long br=0, x, n, m;
pair<long long, long long> buses[500005];
long long tabl[1005][1005];
vector<int> s;

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    x=X;
    s=S;
    m=M;
    for(int i=0; i<N; i++)
    {
        if(W[i]<=X) continue;
        br++;
        buses[br-1]={T[i], W[i]};
    }
    sort(buses, buses+br);
    N=br;
    n=N;
    for(int i=0; i<N; i++) tabl[0][i]=buses[i].first;
    for(int i=1; i<M; i++)
    {
        for(int j=0; j<N; j++)
        {
            buses[j].first+=buses[j].second*(S[i]-S[i-1]);
            if(j) buses[j].first=max(buses[j].first, buses[j-1].first);
            tabl[i][j]=buses[j].first;
        }
        sort(buses, buses+br);
    }
}

long long arrival_time(long long Y)
{
    int id=0;
    while(id<n && tabl[0][id]<Y) id++;
    for(int i=1; i<m; i++)
    {
        Y+=x*(s[i]-s[i-1]);
        if(id && tabl[i][id-1]>Y) Y=tabl[i][id-1];
        while(id && tabl[i][id-1]>=Y) id--;
        //cout<<Y<<' '<<id<<endl;
    }
    return Y;
}

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