Submission #202252

#	Time	Username	Problem	Language	Result	Execution time	Memory
202252		grt	Segway (COI19_segway)	C++17	15 / 100	18 ms	1140 KiB

segway

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

struct Trip {
	int a,b,c;
	bool operator < (const Trip&Tr) const {
		return a<Tr.a;
	}
};

const int nax = 20*1000+10,kax = 300+5;
int n,m;
Trip v[nax];
int station[kax];
int nxt[kax][21];
int cnt[kax];
bool visited[nax][kax];
int ans[nax];
priority_queue<Trip>PQ;

int driving_time(int id,int x,int y) {
	int t = 0;
	t += (min(y,100)-min(x,100))*v[id].a;
	x = max(100,x); y = max(100,y);
	t += (min(y,200)-min(x,200))*v[id].b;
	x = max(200,x); y = max(200,y);
	t += (y-x)*v[id].c;
	return t;
}

int main() {_
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>v[i].a>>v[i].b>>v[i].c;
	}
	cin>>m;
	for(int i=1; i<=m; i++) {
		cin>>station[i];
	}
	for(int i=1; i<=m; i++) {
		nxt[i][20] = m+1;
		for(int j=i+1; j<=m; j++) {
			if(nxt[i][min(19,station[j]-station[i])]==0) {
				nxt[i][min(19,station[j]-station[i])]=j;
			} else {
				break;
			}
		}
		for(int j=19; j>=0; j--) {
			if(nxt[i][j]==0) nxt[i][j] = nxt[i][j+1];
		}
	}
	if(m==0) {
		for(int i=1; i<=n; i++) {
			cout<<driving_time(i,0,300)<<"\n";
		}
		return 0;
	}
	for(int i=1; i<=n; i++) {
		PQ.push({-driving_time(i,0,station[1]),i,1});
	}
	station[m+1] = 300;
	int last = -1;
	vi delta = {};
	while(!PQ.empty()) {
		Trip tp = PQ.top();
		tp.a = -tp.a;
		if(tp.a!=last) {
			for(auto x:delta) {
				cnt[x]++;
			}
			last = tp.a;
			delta.clear();
		}
		delta.PB(tp.c);
		PQ.pop();
		// cover case when more than one driver have same time
		if(tp.c==m+1) {
			ans[tp.b] = tp.a;
			continue;
		}
		int d = min(300-station[tp.c],cnt[tp.c]%20);
		int nx = nxt[tp.c][d];
		for(int i=tp.c+1; i<nx; i++) delta.PB(i);
		int t1 = tp.a+driving_time(tp.b,station[tp.c]+d,station[nx])+d;
		PQ.push({-t1,tp.b,nx});
	}
	for(int i=1; i<=n; i++) {
		cout<<ans[i]<<"\n";
	}	
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 45