Submission #1177512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177512		alexander707070	Overtaking (IOI23_overtaking)	C++20	39 / 100	3594 ms	24392 KiB

overtaking

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

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

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

long long simulate(){
	for(int i=1;i<=m;i++)st[i].clear();
	
	for(int i=1;i<=n+1;i++){
		arrive[1][i]=start[i];
		st[1].push_back({start[i],i});
	}
	sort(st[1].begin(),st[1].end());

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

		long long maxtim=0, pt=0;
		long long dist=station[i]-station[i-1];

		for(int f=0;f<n+1;f++){
			int curr=st[i-1][f].second;

			while(pt<n+1 and st[i-1][pt].first < arrive[i-1][curr]){
				maxtim=max(maxtim,st[i-1][pt].first + dist*speed[st[i-1][pt].second]);
				pt++;
			}

			arrive[i][curr]=max(maxtim , arrive[i-1][curr] + dist*speed[curr]);

			st[i].push_back({arrive[i][curr],curr});
		}

		sort(st[i].begin(),st[i].end());
	}

	return arrive[m][n+1];
}

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

	speed[n+1]=X;
	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];
}

long long arrival_time(long long Y){
	start[n+1]=Y;
	return simulate();
}

/*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: 0 / 26
• Subtask 5: 0 / 35