Cod sursa(job #141731)

Utilizator andrei.12Andrei Parvu andrei.12 Data 23 februarie 2008 18:04:43
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 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 = 0;      
	
    st = v[1].t;      
    for (i = 1; i <= n; i ++){      
        if (val <= v[i].c)      
            rz += val;      
        
        x = rz - c*(v[i].t - st+1);      
        //printf("%d\n", rz);      
        if (x > raspuns)      
            raspuns = x;      
		
        if (x <= 0)      
            rz = 0, st = v[i+1].t;      
		
        //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("%d\n", raspuns);      
    
    return 0;      
}