Mai intai trebuie sa te autentifici.
Cod sursa(job #828199)
| Utilizator | Data | 3 decembrie 2012 13:03:48 | |
|---|---|---|---|
| Problema | Carnati | Scor | 60 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.9 kb |
#include<cstdio>
#include<algorithm>
using namespace std;
struct structura
{
int x;
int y;
};
bool cmp(structura a,structura b)
{
return a.x<b.x;
}
int n,c,i,pret,j,pe;
long long maxim,sum;
structura v[2001];
int main()
{
freopen("carnati.in","r",stdin);
freopen("carnati.out","w",stdout);
scanf("%d%d",&n,&c);
for(i=1; i<=n; i++)
scanf("%d%d",&v[i].x,&v[i].y);
sort(v+1,v+n+1,cmp);
for(i=1; i<=n; i++)
{
pret=v[i].y;
sum=0;
for(j=1; j<=n; j++)
{
if(sum<0)
{
pe=1;
sum=0;
}
if(v[j].y>=pret)
sum+=pret;
if(!pe)
sum-=(v[j].x-v[j-1].x)*c;
pe=0;
if(sum>maxim)
maxim=sum;
}
}
printf("%lld",maxim-c);
}
