Cod sursa(job #210776)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 29 septembrie 2008 00:02:18
Problema Gardieni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define maxn 50010
#define maxx 30
#define inf 2000000
#define ll long long

int n, m, l;
int a[maxn], b[maxn], c[maxn], p[maxn];
int s[maxx];
ll sol;

int cmp(int x, int y)
{
	return a[x] < a[y];
}

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

	scanf("%d %d ", &n, &m);

	int i, j, k, best;

	for (i=1; i<=n; i++) 
	{
		scanf("%d %d %d ", &a[i], &b[i], &c[i]);
		p[i] = i;
	}

	sort(p+1, p+n+1, cmp);

	j = 1;

	for (i=1; i<=m; i++)
	{
		for (; j<=n && a[p[j]]==i; j++) s[++l] = p[j];

		for (k=1; k<=l; k++) 
			if (i > b[s[k]]) s[k--] = s[l--];

		best = inf;

		for (k=1; k<=l; k++) 
			if (c[s[k]] < best) best = c[s[k]];

		sol += best;
	}

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

	return 0;
}