Submission #39387

#	Time	Username	Problem	Language	Result	Execution time	Memory
39387		14kg	코알라 (JOI13_koala)	C++11	100 / 100	99 ms	5888 KiB

koala

#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 (stderr)

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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50