Cod sursa(job #517616)

Utilizator dragan1alexDragan Andrei Alexandru dragan1alex Data 29 decembrie 2010 13:01:51
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<fstream>
using namespace std;
ifstream fin("carnati.in");
ofstream fout("carnati.out");
struct client{int t,p;};
int n,c;
client v[2001];

void poz(int st,int dr,int &p){
	int i=st,j=dr,d=0;
	client aux;
	while(i<j){
		if(v[i].t>v[j].t){
			aux=v[i];
			v[i]=v[j];
			v[j]=aux;
			d=1-d;
		}
		i+=d;
		j-=1-d;
	}
	p=i;
}
void quicksort(int st,int dr){
	int p;
	if(st<dr){
		poz(st,dr,p);
		quicksort(st,p-1);
		quicksort(p+1,dr);
	}
}

inline int profit(int p){
    int sc=0,prof=INT_MIN,i,u=-1;
    for(i=1;i<=n;i++){
        if(v[i].p<p)
            continue;
        if(u!=-1&&sc-(v[i].t-u-1)*c>0)
            sc+=p-(v[i].t-u)*c;
        else
            sc=p-c;
        if(sc>prof)
            prof=sc;
        u=v[i].t;
    }  
    return prof;
}
	

int main(){
    int i,nr,profmax=INT_MIN;
    fin>>n>>c;
    for(i=1;i<=n;i++)
    fin>>v[i].t>>v[i].p;
    quicksort(1,n);
    for(i=1;i<=n;i++)
        if(profit(v[i].p)>profmax)
           profmax=profit(v[i].p);
         
    fout<<profmax;
         
return 0;
}