Submission #1071264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071264		Muhammad_Aneeq	Overtaking (IOI23_overtaking)	C++17	65 / 100	3559 ms	26964 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];
map<int,vector<pair<long long,long long>>>mx;
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);
			mx[i].push_back({j.first,pre});
		}
		d.clear();
		for (int j=0;j<n;j++)
			d[reach[j][i]].push_back(j);
	}
}	
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;
	comp();
}
long long arrival_time(long long Y)
{
	long long cos=Y;
	for (int i=1;i<m;i++)
	{
		long long cos1=cos+(stops[i]-stops[i-1])*sp[n];
		pair<long long,long long>f={cos,-1};
		int z=lower_bound(begin(mx[i]),end(mx[i]),f)-begin(mx[i]);
		if (z!=0)
		{
			z--;
			cos1=max(cos1,mx[i][z].second);
		}
		cos=cos1;
	}
	return cos;
}

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