Cod sursa(job #2712166)

Utilizator andreiiorgulescuandrei iorgulescu andreiiorgulescu Data 25 februarie 2021 11:53:00
Problema Orase Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("orase.in");
ofstream out("orase.out");

struct oras
{
    int d;
    int l;
};

bool cmp(oras A,oras B)
{
    if (A.d != B.d)
        return A.d < B.d;
    else
        return A.l > B.l;
}

int main()
{
    ios_base::sync_with_stdio(false);
    in.tie(NULL);
    int n,m,i,j,s,smax = 0;
    vector<oras>a;
    oras x;
    in >> m >> n;
    for (i = 1; i <= n; i++)
    {
        in >> x.d >> x.l;
        a.push_back(x);
    }
    sort(a.begin(),a.end(),cmp);
    /*
    for (i = 1; i < n; i++)
    {
        if (a[i].d == a[i - 1].d and a[i].l > a[i - 1].l)
        {
            s = a[i].l + a[i - 1].l;
            if (s > smax)
                smax = s;
            a.erase(a.begin() + i);
            i--;
            n--;
        }
        else if (a[i].d == a[i - 1].d)
        {
            s = a[i].l + a[i - 1].l;
            if (s > smax)
                smax = s;
            a.erase(a.begin() + i);
            i--;
            n--;
        }
    }
    i = 1;
    while (n > 1)
    {
        s = a[i].l + a[i - 1].l + a[i].d - a[i - 1].d;
        if (s > smax)
            smax = s;
        if (a[i].l <= a[i - 1].l + a[i].d - a[i - 1].d)
        {
            a.erase(a.begin() + i);
            n--;
        }
        else
        {
            a.erase(a.begin() + i - 1);
            n--;
        }
    }
    */
    i = 0;
    j = 1;
    while (n > 1)
    {
        s = a[j].l + a[i].l + a[j].d - a[i].d;
        if (s > smax)
            smax = s;
        if (a[j].l >= a[i].l + a[j].d - a[i].d)
        {
            i = j + 1;
            swap(i,j);
            n--;
        }
        else
        {
            j++;
            n--;
        }
    }
    out << smax;
    return 0;
}