Cod sursa(job #2394273)

Utilizator moltComan Calin molt Data 1 aprilie 2019 15:00:40
Problema Orase Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 50000;

int m,n;
int d[NMAX + 5], l[NMAX + 5];
long long difmax;
long long rez;
int mx[1000005];
bool ap[1000005];

vector<pair<int, int>> v;

int main()
{
    in>>m>>n;
    for (int i = 1; i <= n; ++i)
    {
        int dd,ll;
        in>>dd>>ll;
        if (mx[dd] == 0) mx[dd] = ll;
        else if (ll > mx[dd]) mx[dd] = ll;
        d[i] = dd;
        l[i] = ll;
    }
    for (int i = 1; i <= n; ++i)
        if (ap[d[i]] == false)
        {
            v.push_back({d[i], mx[d[i]]});
            ap[d[i]] = true;
        }

    sort(v.begin(), v.end());
    for (vector<pair<int,int >> :: iterator it = v.begin(); it != v.end(); ++it)
    {
        int d = it -> first;
        int l = it -> second;
        difmax = max(difmax, (long long) l - d);
    }
    for (vector<pair<int, int>> :: iterator it = v.begin(); it != v.end(); ++it)
    {
        int d = it -> first;
        int l = it -> second;
        rez = max(rez, (long long) d + l + difmax);
    }
    out<<rez;
    return 0;
}