Submission #1233924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233924		MuhammadSaram	Overtaking (IOI23_overtaking)	C++20	39 / 100	53 ms	24136 KiB

overtaking

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

using namespace std;

#define ll long long
#define all(v) v.begin(), v.end()

const int M = 1000;

ll pre[M][M],x;
vector<pair<ll,int>> v[M];
vector<int> s;
int m;

void init(int l, int n, vector<long long> T, vector<int> w, int X, int m1, vector<int> S)
{
	x=X,m=m1,s=S;
	for (int i=0;i<n;i++)
	{
		if (w[i]<=x) continue;
		v[0].push_back({T[i],w[i]});
	}
	for (int i=0;i+1<m;i++)
	{
		sort(all(v[i]));
		ll mx=0,mx1=0;
		for (int j=0;j<v[i].size();j++)
		{
			ll t=v[i][j].first,w=v[i][j].second;
			if (j && v[i][j-1].second!=v[i][j].second)
				mx=mx1;
			mx1=max(mx1,t+w*(s[i+1]-s[i]));
			v[i+1].push_back({max(mx,t+w*(s[i+1]-s[i])),w});
			pre[i][j+1]=v[i+1].back().first;
		}
	}
	
    return;
}

long long arrival_time(long long y)
{
	for (int i=0;i+1<m;i++)
	{
		int id=lower_bound(all(v[i]),make_pair(y,0))-begin(v[i]);
		y=max(pre[i][id],y+x*(s[i+1]-s[i]));
	}
    return y;
}

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