oj.uz

Submission #39387

# Submission time Handle Problem Language Result Execution time Memory
39387 2018-01-13T11:34:25 Z 14kg 코알라 (JOI13_koala) C++11
100 / 100
 99 ms 5888 KB 
#include <stdio.h>
#include <algorithm>
#include <queue>
#define LL long long

using namespace std;
int S, E, J, n;
long long P;
pair<int, long long> in[100001];
priority_queue<pair<long long, int> > Q;

int main() {
	int t;
	pair<long long, int> path = { 0,-1 };

	scanf("%d %d %d %lld %d", &S, &E, &J, &P, &n);
	for (int i = 1; i <= n; i++) scanf("%d %lld", &in[i].first, &in[i].second);
	sort(in + 1, in + n + 1);
	
	Q.push({ 0,S });
	for (int i = 1; i <= n; i++) {
		while (Q.top().second < in[i].first) {
			if (path.second>=Q.top().second) Q.pop();
			else {
				path = Q.top(), Q.pop();
				t = (in[i].first - path.second) / J;
				if ((LL)path.second + (LL)J*(LL)t < (LL)in[i].first) t++;

				Q.push({ path.first - P*(LL)t, path.second + J*t });
			}
		}
		Q.push({ Q.top().first + in[i].second, in[i].first });
	}
	while (Q.top().second < E) {
		path = Q.top(), Q.pop();
		t = (E - path.second) / J;
		if ((LL)path.second + (LL)J*(LL)t < (LL)E) t++;

		Q.push({ path.first - P*(LL)t, path.second + J*t });
	}
	printf("%lld", Q.top().first);
}

Compilation message

koala.cpp: In function 'int main()':
koala.cpp:16:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %lld %d", &S, &E, &J, &P, &n);
                                               ^
koala.cpp:17:76: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%d %lld", &in[i].first, &in[i].second);
                                                                            ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2732 KB Output is correct
2 Correct 0 ms 2732 KB Output is correct
3 Correct 0 ms 2732 KB Output is correct
4 Correct 0 ms 2732 KB Output is correct
5 Correct 0 ms 2732 KB Output is correct
6 Correct 0 ms 2732 KB Output is correct
7 Correct 0 ms 2732 KB Output is correct
8 Correct 0 ms 2732 KB Output is correct
9 Correct 0 ms 2732 KB Output is correct
10 Correct 0 ms 2732 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2732 KB Output is correct
2 Correct 69 ms 2732 KB Output is correct
3 Correct 23 ms 2732 KB Output is correct
4 Correct 99 ms 2732 KB Output is correct
5 Correct 23 ms 2732 KB Output is correct
6 Correct 26 ms 2732 KB Output is correct
7 Correct 39 ms 2732 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 2732 KB Output is correct
2 Correct 69 ms 3004 KB Output is correct
3 Correct 56 ms 5888 KB Output is correct
4 Correct 63 ms 5888 KB Output is correct
5 Correct 33 ms 2732 KB Output is correct
6 Correct 29 ms 4352 KB Output is correct