oj.uz

Submission #117831

# Submission time Handle Problem Language Result Execution time Memory
117831 2019-06-17T08:36:41 Z 임유진(#2881) Segway (COI19_segway) C++14
15 / 100
 15 ms 1148 KB 
#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[300];
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 = 0; i < M; i++) scanf("%d", p + i);
	p[M] = 300;

	//printf("%d %d\n", N, M);

	for (int i = 0; i < N; i++) {
		if (p[0] > 200) pq.push(make_pair(100 * v[i][0] + 100 * v[i][1] + (p[0] - 200) * v[i][2], i));
		else if (p[0] > 100) pq.push(make_pair(100 * v[i][0] + (p[0] - 100) * v[i][1], i));
		else pq.push(make_pair(v[i][0] * p[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) {
			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

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:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < M; i++) scanf("%d", p + i);
                              ~~~~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 15 ms 1148 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 15 ms 1148 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Incorrect 2 ms 256 KB Output isn't correct
9 Halted 0 ms 0 KB -