Submission #117897

#	Time	Username	Problem	Language	Result	Execution time	Memory
117897		imyujin	Segway (COI19_segway)	C++14	15 / 100	16 ms	1396 KiB

segway

#include<stdio.h>
#include<queue>
#include<vector>

using namespace std;

#define MAXN 20005

typedef pair<int, int> pi;

int v[MAXN][3];
int x[MAXN];
int ans[MAXN];
int cnt[305];
vector<int> ve;
int cntt = 0;

int main() {
	int N, M;
	int p[300];
	priority_queue<pi, vector<pi>, greater<pi> > pq;

	//freopen("input.txt", "r", stdin);

	scanf("%d", &N);
	for (int i = 0; i < N; i++) for (int j = 0; j < 3; j++) scanf("%d", &v[i][j]);
	scanf("%d", &M);
	for (int i = 1; i <= M; i++) scanf("%d", p + i);

	p[0] = 0;
	p[M+1] = 300;

	for (int i = 0; i < N; i++) pq.push(make_pair(0, i));

	while (!pq.empty()) {
		pi t = pq.top();
		//printf("[%d %d]\n", t.first, t.second);
		pq.pop();
		int k = x[t.second]+1;
		if (k <= M+1) {
			while (k <= M && p[k] < p[x[t.second]] + cnt[x[t.second]]%20) k++;
			int ti = t.first + cnt[x[t.second]]%20;
			int po = p[x[t.second]] + cnt[x[t.second]]%20;
			//printf("%d %d %d\n", k, po, p[k]);
			if (po > p[k]) ti -= po - 300;
			else if (po < 100) {
				if (p[k] < 100) ti += (p[k] - po) * v[t.second][0];
				else if (p[k] < 200) ti += (100 - po) * v[t.second][0] + (p[k] - 100) * v[t.second][1];
				else ti += (100 - po) * v[t.second][0] + 100 * v[t.second][1] + (p[k] - 200) * v[t.second][2];
			}
			else if (po < 200) {
				if (p[k] < 200) ti += (p[k] - po) * v[t.second][1];
				else ti += (200 - po) * v[t.second][1] + (p[k] - 200) * v[t.second][2];
			}
			else ti += (p[k] - po) * v[t.second][2];
			pq.push(make_pair(ti, t.second));
			//printf("{%d %d}\n", ti, t.second);
			cntt++;
			//if (cntt > 20) return 0;
		}
		else ans[t.second] = t.first;
		for (int i = x[t.second]; i < k; i++) ve.push_back(i);
		if (pq.empty() || t.first != pq.top().first) while (!ve.empty()) {
			cnt[ve.back()]++;
			ve.pop_back();
		}
		x[t.second] = k;
	}

	for (int i = 0; i < N; i++) printf("%d\n", ans[i]);
	return 0;
}

Compilation message (stderr)

segway.cpp: In function 'int main()':
segway.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
segway.cpp:26:63: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < N; i++) for (int j = 0; j < 3; j++) scanf("%d", &v[i][j]);
                                                          ~~~~~^~~~~~~~~~~~~~~~
segway.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &M);
  ~~~~~^~~~~~~~~~
segway.cpp:28:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= M; i++) scanf("%d", p + i);
                               ~~~~~^~~~~~~~~~~~~

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