Cod sursa(job #127236)

Utilizator marinMari n marin Data 23 ianuarie 2008 17:07:37
Problema Gardieni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
// minim[i] = costul minim al unui interval ce contine punctul i
//   2. pentru fiecare moment i de la 1 la T
//   3.        minim[i] = INFINIT // o valoare foarte mare
//   4. pentru fiecare interval i (x[i], y[i]) de cost c[i]
//   5.        pentru fiecare moment j de la x[i] la y[i]
//   6.               daca c[i] < minim[j]
//   7.                    minim[j] = c[i]
//   8. Cost_Total = 0
//   9. pentru fiecare moment i de la 1 la T
//  10.        Cost_Total = Cost_Total + minim[i]
// 1 = N = 50 005
// 1 = T = 1 000 000
// 1 = a = b = T
// 1 = c = 220
#include <stdio.h>
#define DIM 1000001
struct firm{
  long int a;
  long int b;
  long int c;
} x[DIM];
long int m[DIM];
long int n,t,i,j;
long long total;

int main(){
  FILE *f = fopen("gardieni.in","r");
  fscanf(f,"%ld %ld",&n,&t);
  for (i=1;i<=n;i++)
    fscanf(f,"%ld %ld %ld",&x[i].a,&x[i].b,&x[i].c);
  fclose(f);
  for (i=1;i<=t;i++)
    m[i]=1l<<30;
  for (i=1;i<=n;i++)
    for (j=x[i].a;j<=x[i].b;j++)
      if (x[i].c<m[j])
	m[j]=x[i].c;
  total=0;
  for (i=1;i<=t;i++)
    total+=m[i];
  FILE *g = fopen("gardieni.out","w");
  fprintf(g,"%lld",total);
  fclose(g);

  return 0;
}