Pagini recente » Cod sursa (job #1098167) | Cod sursa (job #2912467) | Cod sursa (job #638661) | Cod sursa (job #1511432) | Cod sursa (job #1767501)
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
pair <int,int> v[50001];
int d[50001];
int main()
{
FILE *fin=fopen ("orase.in","r");
FILE *fout=fopen ("orase.out","w");
int m,n,i,smax;
fscanf (fin,"%d%d",&m,&n);
for (i=1;i<=n;i++)
fscanf (fin,"%d%d",&v[i].first,&v[i].second);
sort (v+1,v+n+1);
// d[i]= subsecv de s max care se term pe poz i
// d[i]=max(d[i-1]+v[i].second , (v[i].first-v[i-1].first)+d[i-1])
d[1]=v[1].second+v[1].first;
smax=0;
for (i=2;i<=n;i++){
if (i!=n && d[i-1]+v[i].second > (v[i].first-v[i-1].first)+d[i-1]){
smax=max(smax,d[i-1]+v[i].second);
d[i]=v[i].second;
}
else d[i]=d[i-1]+v[i].first-v[i-1].first;
}
smax=max(smax,d[n]+v[n].second);
fprintf (fout,"%d",smax);
return 0;
}