Cod sursa(job #1512356)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 27 octombrie 2015 22:30:38
Problema Reconst Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <cstdio>
#include <algorithm>

#define DIM 2048
#define ll long long
#define x first
#define y second.first
#define z second.second
using namespace std;

ll D[DIM], W[DIM], Sol[DIM], N, M;
pair <ll, pair <ll, ll> > V[DIM];

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

    scanf ("%d %d", &N, &M);

    for (int i = 1; i <= M; i ++)
    {
        scanf ("%d", &V[i].x);
        scanf ("%d", &V[i].y);
        scanf ("%d", &V[i].z);
    }

    sort (V + 1, V + M + 1);

    for (int i = 1; i <= M; i ++)
        W[V[i].x] = i;

    for (int i = N; i >= 1; i --)
    {
        if (W[i] != 0)
            Sol[i] = V[W[i]].z - (D[V[W[i]].x+1] - D[V[W[i]].y+1]);
        D[i] = D[i+1] + Sol[i];
    }

    for (int i = 1; i <= N; i ++)
        printf ("%d ", Sol[i]);

    fclose (stdin );
    fclose (stdout);

    return 0;
}