Cod sursa(job #2151674)

Utilizator ivddabDabelea Ioana-Viviana ivddab Data 4 martie 2018 18:58:29
Problema Orase Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#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;
}