Cod sursa(job #127231)

Utilizator marinMari n marin Data 23 ianuarie 2008 17:03:45
Problema Gardieni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 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,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<<31;
  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,"%ld",total);
  fclose(g);

  return 0;
}