Submission #1244708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244708		alexander707070	Overtaking (IOI23_overtaking)	C++20	65 / 100	3592 ms	33352 KiB

overtaking

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

int n,m;
int station[MAXN];
long long speed[MAXN],start[MAXN];

pair<long long,int> st[MAXN][MAXN];
long long maxtim[MAXN][MAXN];
long long arrive[MAXN][MAXN];

bool cmp(pair<long long,int> fr,pair<long long,int> sc){
    if(fr.first!=sc.first)return fr.first<sc.first;
    return speed[fr.second] < speed[sc.second];
}

void build_timetable(){

    for(int i=1;i<=n;i++){
		arrive[1][i]=start[i];
		st[1][i]={start[i],i};
	}

    sort(st[1]+1,st[1]+n+1,cmp);

    for(int i=2;i<=m;i++){

		long long dist=station[i]-station[i-1];

		for(int f=1;f<=n;f++){

            int curr=st[i-1][f].second;

			maxtim[i-1][f]=st[i-1][f].first + dist*speed[curr];
			maxtim[i-1][f]=max(maxtim[i-1][f],maxtim[i-1][f-1]);

            arrive[i][curr]=maxtim[i-1][f];
            st[i][f]={arrive[i][curr],curr};
		}

		sort(st[i]+1,st[i]+n+1,cmp);
	}
}

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S){
	n=N; m=M;

	for(int i=1;i<=m;i++)station[i]=S[i-1];
	for(int i=1;i<=n;i++)speed[i]=W[i-1];
	for(int i=1;i<=n;i++)start[i]=T[i-1];

    int sm=0;
    for(int i=1;i<=n;i++){
        if(speed[i]<=X)continue;

        sm++;
        speed[sm]=speed[i];
        start[sm]=start[i];
    }

    n=sm;
    speed[n+1]=X;

	build_timetable();
}

long long arrival_time(long long Y){
	long long tim=Y;

	for(int i=2;i<=m;i++){
		long long dist=station[i]-station[i-1];
		int l=0,r=n+1,tt;

		while(l+1<r){
			tt=(l+r)/2;

			if(st[i-1][tt].first<tim){
				l=tt;
			}else{
				r=tt;
			}
		}

		tim=max(maxtim[i-1][l] , tim+speed[n+1]*dist);
	}

	return tim;
}

/*int main(){

	init(6, 4, {20, 10, 40, 0}, {5, 20, 20, 30}, 10, 4, {0, 1, 3, 6});

	cout<<arrival_time(0)<<"\n";
	cout<<arrival_time(50)<<"\n";

	return 0;
}*/

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