Pagini recente » Cod sursa (job #2656307) | Cod sursa (job #3230012) | Cod sursa (job #1945463) | Cod sursa (job #2311683) | Cod sursa (job #517609)
Cod sursa(job #517609)
#include<fstream>
using namespace std;
ifstream fin("carnati.in");
ofstream fout("carnati.out");
struct om{
int t,p;
};
om v[2001];
int c,n;
void poz(int st,int dr,int &p){
int i=st,j=dr,d=0;
om 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 quicky(int st,int dr){
int p;
if(st<dr){poz(st,dr,p);
quicky(st,p-1);
quicky(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;
//quicky(1,n);
for(i=1;i<=n;i++)
if(profit(v[i].p)>profmax)
profmax=profit(v[i].p);
fout<<profmax;
return 0;
}