Mai intai trebuie sa te autentifici.
Cod sursa(job #854743)
Utilizator | Data | 13 ianuarie 2013 22:20:06 | |
---|---|---|---|
Problema | Carnati | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.87 kb |
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("carnati.in");
ofstream g("carnati.out");
int n,c;
struct nr
{
int t,p;
};
nr a[2001];
int cmp(nr a, nr b)
{
return a.t<b.t;
}
int cost(int pret)
{
int i,u=-1,pretmax=-1,pretc;
for(i=1;i<=n;i++)
{
if(a[i].p<pret)
continue;
if(u!=-1)
{
pretc=pretc-(a[i].t-a[u].t-1)*c;
if(pretc<0)
pretc=0;
}
else
pretc=0;
u=i;
pretc=pretc+pret-c;
if(pretc>pretmax)
pretmax=pretc;
}
return pretmax;
}
int main()
{
int pret,pmax=-1,i;
f>>n>>c;
for(i=1;i<=n;i++)
f>>a[i].t>>a[i].p;
sort(a+1,a+1+n,cmp);
for(i=1;i<=n;i++)
{
pret=cost(a[i].p);
if(pret>pmax)
pmax=pret;
}
g<<pmax;
return 0;
}