Submission #1071124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071124		Muhammad_Aneeq	Overtaking (IOI23_overtaking)	C++17	39 / 100	3553 ms	8432 KiB

overtaking

#include <vector>
#include <map>
#include <iostream>
using namespace std;
int const N=1010,M=1010;
long long reach[N][M]={};
int n,m;
long long st[N],sp[N];
int stops[N];
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=0;i<n;i++)
		st[i]=T[i];
	for (int i=0;i<n;i++)
		sp[i]=W[i];
	for (int i=0;i<m;i++)
		stops[i]=S[i];
	sp[n]=X;
}
void comp()
{
	map<long long,vector<int>>d;
	for (int i=0;i<=n;i++)
	{
		reach[i][0]=st[i];
		d[st[i]].push_back(i);
	}
	for (int i=1;i<m;i++)
	{
		long long pre=0;
		for (auto j:d)
		{
			long long mn=0;
			for (auto k:j.second)
			{
				reach[k][i]=reach[k][i-1]+sp[k]*(stops[i]-stops[i-1]);
				reach[k][i]=max(pre,reach[k][i]);
				mn=max(mn,reach[k][i]);
			}
			pre=max(pre,mn);
		}
		d.clear();
		for (int j=0;j<=n;j++)
			d[reach[j][i]].push_back(j);
	}
}	
long long arrival_time(long long Y)
{
	st[n]=Y;
	comp();
	return reach[n][m-1];
}

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