Cod sursa(job #2617706)

Utilizator PopescuAndreiAlexandruPopescu Andrei Alexandru PopescuAndreiAlexandru Data 22 mai 2020 17:30:45
Problema Orase Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

const int DIM = 1000005;

long long n,m,x,y,DP[DIM],S[DIM],pos,ans;

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        DP[x]=max(DP[x],y);
    }
    for(int i=0;i<=n;i++)
    {
        if(!S[i] && DP[i])
        {
            S[i]=DP[i];
            pos=i+1;
            break;
        }
    }
    for(int i=pos;i<=n;i++)
    {
        S[i]=S[i-1]+1;
        if(DP[i]>S[i])
            S[i]=DP[i];
        if(S[i] && DP[i])
        {
            long long sum=S[i]+DP[i];
            if(sum>ans)
                ans=sum;
        }
    }
    fout<<ans<<'\n';
}