Submission #1222429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222429		thelegendary08	Overtaking (IOI23_overtaking)	C++17	39 / 100	3592 ms	16240 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
#define int long long
#define f0r(i,n) for(int i = 0; i<n; i++)
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define mii map<int,int>
#define pii pair<int,int>
#define vpii vector<pii>
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define vb vector<bool>
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;
int l, n, nspeed, m;
vi t, speed, s;
void init(signed L, signed N, std::vector<long long> T, std::vector<signed> W, signed X, signed M, std::vector<signed> S)
{	
	l=L; n=N; t=T; nspeed=X; m=M; 
	speed.resize(n); f0r(i,n)speed[i] = W[i];
	s.resize(m); f0r(i,m)s[i] = S[i];
    return;
}

long long arrival_time(long long y)
{
	if(false){
		if(nspeed <= speed[0])return y + l * nspeed;
		else{
			if(y <= t[0])return y + l * nspeed;
			else{
				double dif = (y - t[0]) / (speed[0] + 0.0); //position of 0 when 1 departs
				double nxtp = dif * (nspeed - speed[0]); // time taken to catch up
				double pos = nxtp / (nspeed + 0.0);
				int lo = 0; int hi = m; //find first sorting station >= pos
				while(lo < hi){
					int mid = lo + (hi - lo) / 2;
					if(s[mid] >= pos){
						hi = mid;
					}
					else{
						lo = mid + 1;
					}
				}
				if(lo == m)return y + l * nspeed;
				else{
					return t[0] + speed[0] * s[lo] + (s[m-1] - s[lo]) * nspeed;
				}
			}
		}
	}
	else{
		vector<vi> ex(n+1, vi(m));
		vector<vi> ac(n+1, vi(m));
		f0r(i, n){
			ex[i][0] = t[i]; 
			ac[i][0] = t[i];
		}
		ex[n][0] = y; ac[n][0] = y;
		for(int i = 1; i<m; i++){
			f0r(j,n){
				// cout<<ac[j][i-1]<<' '<<speed[j]<<' '<<s[i] - s[i-1]<<'\n';
				ex[j][i] = ac[j][i-1] + speed[j] * (s[i] - s[i-1]);
			}
			ex[n][i] = ac[n][i-1] + nspeed * (s[i] - s[i-1]);
			vpii thing;
			f0r(j, n+1){
				thing.pb(mp(ac[j][i-1], j));
			}
			sort(thing.begin(), thing.end());
			int ptr = 0;
			int rnmx = 0;
			f0r(j, n+1){
				if(ptr <= n && thing[ptr].first != thing[j].first){
					while(ptr != j){
						rnmx = max(rnmx, ex[thing[ptr].second][i]);
						ptr++;
					}
				}
				/*
				if(i == 2){
					cout<<j<<' '<<rnmx<<'\n';
				}
				*/
				ac[thing[j].second][i] = max(rnmx, ex[thing[j].second][i]);
			}
		}
		/*
		f0r(i, n+1){
			f0r(j, m){
				cout<<ex[i][j]<<' ';
			}
			cout<<'\n';
		}
		cout<<'\n';
		*/
		return ac[n][m-1];
		
	}
	
    return 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