Cod sursa(job #2024629)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 20 septembrie 2017 22:26:43
Problema Reconst Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <bits/stdc++.h>

#define MaxN 2005
#define INF 2140000000
#define MOD 1000000007
using namespace std;

FILE *IN,*OUT;

int N,M,out[MaxN];
struct spec
{
    int first,second,sum;
} v[MaxN];

int main()
{
    IN=fopen("reconst.in","r");
    OUT=fopen("reconst.out","w");

    fscanf(IN,"%d%d",&N,&M);

    for(int i=1;i<=M;i++)
        fscanf(IN,"%d%d%d",&v[i].first,&v[i].second,&v[i].sum);
    for(int i=1;i<=N;i++)
    {
        int head=INF,pos=0;
        for(int j=1;j<=M;j++)
            if(v[j].first==i)
            {
                if(head>v[j].second)
                    head=v[j].second,pos=j;
            }
        if(head==INF)
            continue;
        for(int j=1;j<=M;j++)
        {
            if(j==pos)
                continue;
            if(v[j].first==i)
            {
                if(v[j].second==head)
                {
                    swap(v[j],v[M--]);
                    j--;
                    continue;
                }
                v[j].first=head+1;
                v[j].sum-=v[pos].sum;
            }
        }
    }
    for(int i=N;i>0;i--)
        for(int j=1;j<=M;j++)
        {
            if(v[j].first==i)
            {
                out[v[j].first]=v[j].sum;
                for(int k=1;k<=M;k++)
                    if(k!=j&&v[k].first<i&&v[k].second>=i)v[k].sum-=v[j].sum;
                break;
            }
        }
    for(int i=1;i<=N;i++)
        fprintf(OUT,"%d ",out[i]);
    return 0;
}