Submission #852737

#	Time	Username	Problem	Language	Result	Execution time	Memory
852737		Wansur	Overtaking (IOI23_overtaking)	C++17	39 / 100	3541 ms	26220 KiB

overtaking

#include <vector>
#include<bits/stdc++.h>
#define f first
#define s second
#define ent '\n';

using namespace std;
typedef long long ll;
const int mx=1e3+12;

long long pref[mx][mx];
long long d[mx][mx];
long long e[mx][mx];
long long t[mx][mx];
long long tt[mx];
long long w[mx];
long long s[mx];
long long n,m,k,x;

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S){
	n=N;
	x=X;
	m=M;
	for(int i=1;i<=m;i++){
		s[i]=S[i-1];
	}
	for(int i=1;i<=n;i++){
		w[i]=W[i-1];
		tt[i]=T[i-1];
		t[1][i]=tt[i];
		d[1][i]=tt[i];
	}
	sort(d[1]+1,d[1]+n+1);
	for(int i=2;i<=m;i++){
		vector<pair<long long ,int>> pos;
		for(int j=1;j<=n;j++){
			pos.push_back({t[i-1][j],j});
		}
		sort(pos.begin(),pos.end());
		long long mx=0,M=0,c=0,last=-1;
		for(auto To:pos){
			int j=To.s;
			if(To.f!=last){
				M=mx;
			}
			last=To.f;
			mx=max(mx,To.f+w[j]*(s[i]-s[i-1]));
			t[i][j]=max(M,w[j]*(s[i]-s[i-1])+t[i-1][j]);
			c++;
			d[i][c]=t[i][j];
			pref[i][c]=max(pref[i][c-1],w[j]*(s[i]-s[i-1])+t[i-1][j]);
		}
	}
}

long long arrival_time(long long y){
	long long T=y;
	for(int i=2;i<=m;i++){
		int pos=0;
		long long k=T+(s[i]-s[i-1])*x;
		for(int j=1;j<=n;j++){
			if(t[i-1][j]<T){
				k=max(k,t[i-1][j]+(s[i]-s[i-1])*w[j]);
			}
		}
		T=k;
	}
	return T;
}

Compilation message (stderr)

overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:59:7: warning: unused variable 'pos' [-Wunused-variable]
   59 |   int pos=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