Pagini recente » Cod sursa (job #1138126) | Cod sursa (job #1809091) | Cod sursa (job #250058) | Cod sursa (job #2176575) | Cod sursa (job #390591)
Cod sursa(job #390591)
# include <fstream>
using namespace std;
int n, m, d[50003], l[50003], dmax;
void read ()
{
ifstream fin ("orase.in");
fin>>m>>n;
for (int i=1;i<=n;i++)
fin>>d[i]>>l[i];
}
void qsort (int st, int dr)
{
if (st<dr)
{
int i=st, j=dr, dd=0, aux;
while (i<j)
{
if (d[i]>d[j])
{
aux=d[i];d[i]=d[j];d[j]=aux;
aux=l[i];l[i]=l[j];l[j]=aux;
dd=1-dd;
}
i+=dd;
j-=1-dd;
}
qsort (st, i-1);
qsort (i+1, dr);
}
}
void solve ()
{
int c, max, pm;
pm=d[1];
max=l[1];
dmax=-1;
for(int i=2;i<=n;i++)
{
c=l[i]+(d[i]-pm)+max;
if (c>dmax)
dmax=c;
if (l[i]>max+(d[i]-pm))
max=l[i], pm=d[i];
}
}
int main ()
{
read ();
qsort (1, n);
solve ();
ofstream fout ("orase.out");
fout<<dmax;
return 0;
}