Submission #157794

#	Time	Username	Problem	Language	Result	Execution time	Memory
157794		imyujin	Segway (COI19_segway)	C++17	100 / 100	204 ms	25848 KiB

segway

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20010;
const int MAXM = 310;
const int MAXT = 50 * 300 + 10;

int A[MAXN][3], X[MAXM];
vector<int> tl[MAXT];
int cnt[MAXM];
int acc[MAXN], p[MAXN];
int ans[MAXN];

int calt(int x, int t, int pos) {
	//printf("x = %d, t = %d, pos = %d, p[x] = %d, X[p[x]] = %d\n", x, t, pos, p[x], X[p[x]]);
	if(acc[x] >= t + X[p[x]] - pos) return t + X[p[x]] - pos;
	int ans = max(acc[x], t);
	if(acc[x] > t) pos = pos + acc[x] - t;
	if(pos >= 200) return ans + (X[p[x]] - pos) * A[x][2];
	if(pos >= 100) {
		if(X[p[x]] <= 200) return ans + (X[p[x]] - pos) * A[x][1];
		return ans + (200 - pos) * A[x][1] + (X[p[x]] - 200) * A[x][2];
	}
	if(X[p[x]] <= 100) return ans + (X[p[x]] - pos) * A[x][0];
	if(X[p[x]] <= 200) return ans + (100 - pos) * A[x][0] + (X[p[x]] - 100) * A[x][1]; 
	return ans + (100 - pos) * A[x][0] + 100 * A[x][1] + (X[p[x]] - 200) * A[x][2];
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M;

	cin >> N;
	for(int i = 1; i <= N; i++) for(int j = 0; j < 3; j++) cin >> A[i][j];
	cin >> M;
	for(int i = 0; i < M; i++) cin >> X[i];

	sort(X, X + M);
	X[M] = 300;
	for(int i = 1; i <= N; i++) tl[calt(i, 0, 0)].push_back(i);
	for(int i = 0; i < MAXT; i++) {
		for(auto a : tl[i]) {
			//printf("i = %d, a = %d, p[a] = %d\n", i, a, p[a]);
			if(p[a]++ == M) ans[a] = i;
			else {
				if(acc[a] <= i) acc[a] = i + cnt[p[a] - 1] % 20;
				//printf("acc = %d\n", acc[a]);
				tl[calt(a, i, X[p[a] - 1])].push_back(a);
				//printf("%d\n", calt(a, i, X[p[a] - 1]));
			}
		}
		for(auto a : tl[i]) cnt[p[a] - 1]++;
	}

	for(int i = 1; i <= N; i++) cout << ans[i] << "\n";
	return 0;
}

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