Pagini recente » Cod sursa (job #3033202) | Cod sursa (job #2943490) | Cod sursa (job #3272488) | concurs-mihai-patrascu-2013/clasament | Cod sursa (job #127233)
Cod sursa(job #127233)
// 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<<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,"%ld",total);
fclose(g);
return 0;
}