Cod sursa(job #138864)

Utilizator andrei.12Andrei Parvu andrei.12 Data 19 februarie 2008 13:27:23
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<stdio.h>    
#include<algorithm>   
  
using namespace std;   
  
#define lg 2005   
  
int n, c, i, raspuns;   
struct ches{   
    int t, c;   
};   
ches v[lg];   
inline int cmp(ches a, ches b){   
    return (a.t < b.t);   
}   
void check(int val){   
    int i, st = 0, rz = 0, x;   
	
    st = v[1].t-1;   
    for (i = 1; i <= n; i ++){   
        if (val <= v[i].c)   
            rz += val;   
       
        x = rz - c*(v[i].t - st);   
        //printf("%d\n", rz);   
        if (x > raspuns)   
            raspuns = x;   
		
        if (x <= 0)   
            rz = 0, st = v[i+1].t-1;   
		
        //printf("%d %d\n\n", rz, st);   
    }   
}   
void find(){   
    int i;   
  
    for (i = 1; i <= n; i ++)   
        check(v[i].c);   
}   
int main()   
{   
    freopen("carnati.in", "rt", stdin);   
    freopen("carnati.out", "wt", stdout);   
  
    scanf("%d%d", &n, &c);   
    for (i = 1; i <= n; i ++)   
        scanf("%d%d", &v[i].t, &v[i].c);   
           
    sort(v+1, v+n+1, cmp);   
  
    find();   
       
    printf("%u\n", raspuns);   
  
    return 0;   
}