Cod sursa(job #432769)

Utilizator ProtomanAndrei Purice Protoman Data 2 aprilie 2010 19:11:03
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 0.85 kb
#include <algorithm>
#include <stdio.h>
#include <set>

#define MAX 100010
#define ll long long
#define mp make_pair
#define f first
#define s second

using namespace std;

ll sol;
int n, h, u;
multiset <int> setNr;
pair <int, int> fruct[MAX];

int main()
{
	freopen("gutui.in", "r", stdin);
	freopen("gutui.out", "w", stdout);

	scanf("%d %d %d", &n, &h, &u);

	for (int i = 1; i <= n; i++)
		scanf("%d %d", &fruct[i].f, &fruct[i].s);

	sort(fruct + 1, fruct + 1 + n);

	int r = 1;
	for (int i = h % u; i - (h % u) <= h; i += u)
	{
		for (; r <= n && fruct[r].f <= i; r++)
			setNr.insert(fruct[r].s);

		multiset <int>::iterator setNrIt = setNr.end();
		if (setNr.size())
		{
			setNrIt--;

			sol += (ll) (*setNrIt);
			setNr.erase(setNrIt);
		}
	}

	printf("%lld\n", sol);

	fclose(stdin);
	fclose(stdout);
	return 0;
}