Cod sursa(job #1767501)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 29 septembrie 2016 11:59:02
Problema Orase Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#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;
}