Submission #852721

#	Time	Username	Problem	Language	Result	Execution time	Memory
852721		Wansur	Overtaking (IOI23_overtaking)	C++17	10 / 100	6 ms	2584 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<=n;i++){
		w[i]=W[i-1];
		tt[i]=T[i-1];
		s[i]=S[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});
			t[i][j]=t[i-1][j]+w[j]*(s[i]-s[i-1]);
			for(int k=1;k<=n;k++){
				if(t[i-1][k]<t[i-1][j]){
					t[i][j]=max(t[i][j],t[i-1][k]+w[k]*(s[i]-s[i-1]));
				}
			}
		}
//		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]);
//		}
		sort(d[i]+1,d[i]+n+1);
	}
}

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:64:7: warning: unused variable 'pos' [-Wunused-variable]
   64 |   int pos=0;
      |       ^~~

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