Submission #852738

#	Time	Username	Problem	Language	Result	Execution time	Memory
852738		Wansur	Overtaking (IOI23_overtaking)	C++17	65 / 100	3522 ms	27728 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]);
		}
		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;
		for(int l=1,r=n;l<=r;){
			int mid=l+r>>1;
			if(d[i-1][mid]<T){
				pos=mid;
				l=mid+1;
			}
			else{
				r=mid-1;
			}
		}
		T=max((s[i]-s[i-1])*x+T,pref[i][pos]);
	}
	return T;
}

Compilation message (stderr)

overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:62:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |    int mid=l+r>>1;
      |            ~^~

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