Submission #895013

#	Time	Username	Problem	Language	Result	Execution time	Memory
895013		Trisanu_Das	Overtaking (IOI23_overtaking)	C++17	65 / 100	3599 ms	28156 KiB

overtaking

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
 
ll pref[1005][1005], d[1005][1005], e[1005][1005], t[1005][1005], tt[1005], w[1005], s[1005], n ,m, k, x;
 
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, 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 ans = y;
	for(int i = 2; i <= m; i++){
		int pos = 0, l = 1, r = n;
		while(l <= r){
			int mid = (l + r) / 2;
			if(d[i - 1][mid] < ans){
				pos = mid;
				l = mid + 1;
			}
			else r = mid - 1;
		}
		ans = max((s[i] - s[i-1]) * x + ans, pref[i][pos]);
	}
	return ans;
}

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