Cod sursa(job #872354)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 5 februarie 2013 23:05:18
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <algorithm>

using namespace std;

int m, n, sol;
struct oras
{
    int l, d;
};
oras a[50010];

inline void Read()
{
    ifstream f ("orase.in");
    f>>m>>n;
    int i;
    for (i=1; i<=n; i++)
        f>>a[i].d>>a[i].l;
    f.close();
}

inline bool cmp (const oras A, const oras B)
{
    if (A.d == B.d)
        return A.l < B.l;
    return A.d < B.d;
}

inline void Solve()
{
    sort(a+1, a+n+1, cmp);

    // dist i, j = l[i] + d[i] + l[j] - d[j];
    int maxj, i;
    maxj = a[1].l - a[1].d;
    sol = a[2].l + a[2].d + maxj;
    for (i=3; i<=n; i++)
    {
        maxj = max(maxj, a[i-1].l - a[i-1].d);
        sol = max(sol, a[i].l + a[i].d + maxj);
    }
}

inline void Write()
{
    ofstream g("orase.out");
    g<<sol<<"\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}