Cod sursa(job #123167)

Utilizator astronomyAirinei Adrian astronomy Data 14 ianuarie 2008 21:27:56
Problema Gardieni Scor Ascuns
Compilator cpp Status done
Runda Marime 1.13 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

#define pb push_back
#define mp make_pair
#define PII pair<int, int>
#define llong long long
#define x first
#define y second
#define MAXXX 10
#define MIN(a,b) ((a) < (b) ? (a) : (b))

int N, T;
vector< pair<PII, int> > A;
vector< PII > B;

llong solve(void)
{
    llong res = 0, i = 0, p, j, t;

    sort(A.begin(), A.end());
    
    for(t = 1; t <= T; t++)
    {
        while(i < N && A[i].x.x <= t) B.pb(mp(A[i].x.y, A[i].y)), i++;
        for(p = (1<<20)+1, j = 0; j < B.size(); j++)
         if(B[j].x >= t) p = MIN(p, B[j].y);
         else B.erase(B.begin()+j), j--;

        assert(B.size() <= MAXXX);

        res += (llong)p;
    }

    return res;
}

int main(void)
{
    freopen("gardieni.in", "rt", stdin);
    freopen("gardieni.out", "wt", stdout);

    int i, a, b, c;
    
    scanf("%d %d\n", &N, &T);

    for(i = 0; i < N; i++)
        scanf("%d %d %d\n", &a, &b, &c), A.pb(mp(mp(a,b),c));

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

    return 0;
}