Cod sursa(job #142740)

Utilizator andrei.12Andrei Parvu andrei.12 Data 25 februarie 2008 08:37:00
Problema Carnati Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 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){        
	if (a.t != b.t)
		return (a.t < b.t);        
	return (a.c > b.c);
}        
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 = val, st = v[i].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;        
}