Pagini recente » Cod sursa (job #2489710) | Cod sursa (job #2284713) | Cod sursa (job #2904293) | Cod sursa (job #1775920) | Cod sursa (job #2151674)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("orase.in");
ofstream g("orase.out");
int m,n,i,d1,l1,min1,smax,s,k;
int fr[1000001];
struct cit {
int d; int l;
};
cit x[50001];
bool cmp( cit a, cit b ){
return a.d<b.d;
}
int main()
{
f>>m>>n; k=0;
for(i=1;i<=n;i++){
f>>d1>>l1;
if(fr[d1]==0) { k++; fr[d1]=k; x[k].d=d1; x[k].l=l1; }
else { x[fr[d1]].l=max(x[fr[d1]].l,l1); }
}
sort(x+1,x+k+1,cmp);
min1=4000000; smax=-5000000;
// for(i=1;i<=k;i++) g<<x[i].d<<' '<<x[i].l<<'\n';
s=x[1].l;
for(i=2;i<=k;i++){
s+=(x[i].l+(x[i].d-x[i-1].d));
if(smax==-5000000) smax=s;
else if(smax<s-min1) smax=s-min1;
if(min1!=4000000) min1+=min((x[i-1].l+(x[i].d-x[i-1].d)),x[i].l);
else min1=min((x[i-1].l+(x[i].d-x[i-1].d)),x[i].l);
//g<<s<<' '<<min1<<'\n';
}
g<<smax<<'\n';
return 0;
}