Submission #847786

#	Time	Username	Problem	Language	Result	Execution time	Memory
847786		sofapuden	Overtaking (IOI23_overtaking)	C++17	100 / 100	2672 ms	45976 KiB

overtaking

#include<bits/stdc++.h>
#include "overtaking.h"

using namespace std;

typedef long long ll;

vector<pair<ll, int>> arr;
vector<vector<ll>> dp;
vector<vector<ll>> E;
vector<ll> nT;
vector<int> nW, nS;
ll l, n, speed, m;

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S){
	E.resize(M, vector<ll> (N));
	dp.resize(M, vector<ll> (N, -1));
	for(int i = 0; i < N; ++i){
		if(W[i] > X){
			nT.push_back(T[i]);
			nW.push_back(W[i]);
		}
	}
	N = nT.size();
	T = nT;
	W = nW;
	l = L, n = N, speed = X, m = M, nS = S;
	arr.resize(N);
	for(int i = 0; i < N; ++i)arr[i] = {T[i], W[i]};
	sort(arr.begin(),arr.end());
	for(int i = 0; i < N; ++i)E[0][i] = arr[i].first;
	for(int i = 1; i < M; ++i){
		for(int j = 0; j < N; ++j){
			arr[j].first += 1ll * arr[j].second * (S[i] - S[i-1]);
			if(j)arr[j].first = max(arr[j].first, arr[j-1].first);
			E[i][j] = arr[j].first;
		}
		sort(arr.begin(),arr.end());
	}
    return;
}

long long f(int X, int Y){
	auto &d = dp[X][Y];
	if(~d)return d;
	if(Y == 0){
		return d = E[X][Y] + speed * (nS[m - 1] - nS[X]);
	}
	if(E[X][Y] == E[X][Y - 1]){
		return d = f(X, Y - 1);
	}
	//bin search
	for(int i = X + 1; i < m; ++i){
		if(E[X][Y] + speed * (nS[i] - nS[X]) <= E[i][Y-1]) return d = f(i, Y - 1);
	}
	return d = E[X][Y] + speed * (nS[m - 1] - nS[X]);
}

long long arrival_time(long long Y){
	// bin search
	int st = n - 1;
	for(int i = 0; i < n; ++i)if(Y <= E[0][i]){ st = i - 1; break; } 
	if(st == -1){
		return Y + speed * (nS[m-1] - nS[0]);
	}
	for(int i = 1; i < m; ++i){
		if(Y + speed * (nS[i] - nS[0]) <= E[i][st])return f(i, st);
	}
	return Y + speed * (nS[m-1] - nS[0]);
}

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