Cod sursa(job #264758)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 22 februarie 2009 18:23:48
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
FILE*fin=fopen("orase.in","r");
FILE*fout=fopen("orase.out","w");
#define ll long long
#define mkp make_pair
#define pb push_back
#define d first
#define l second
vector<pair<int,int> >towns;
ll best=0,ans=0;
int n,m;
int main()
{
  int a,b,i;
  fscanf(fin,"%d%d",&m,&n);
  for(i=1;i<=n;i++)
  {
    fscanf(fin,"%d%d",&a,&b);
    towns.pb(mkp(a,b));
  }
  sort(towns.begin(),towns.end());
  best=towns[0].l+towns[1].d-towns[0].d;
  towns.pb(mkp(0,0));
  for(i=1;i<n;best+=towns[i+1].d-towns[i].d,i++)
  {
    if(best+towns[i].l>ans) ans=best+towns[i].l;
    if(towns[i].l>best) best=towns[i].l;
  }
  fprintf(fout,"%lld",ans);
  fclose(fin);
  fclose(fout);
  return 0;
}