Cod sursa(job #3254264)

Utilizator Darius1414Dobre Darius Adrian Darius1414 Data 6 noiembrie 2024 20:20:21
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>
#define nmx 100005
#define sqr 317
using namespace std;
int t,n,k,x,y,a,b,c,ct,fin[nmx],mx,prv;
pair <int,int> dp[2*nmx];
map <int,vector<int>> mym;
unordered_map <int,int> rsp;
int main()
{
    ifstream f ("heavymetal.in");
    ofstream g ("heavymetal.out");
    f>>n;
    for (int i=1; i<=n; i++)
    {
        f>>x>>y;
        mym[x].push_back(i);
        mym[y].push_back(i);
        fin[i]=y;
    }
    for (auto it : mym)
    {
        //cout<<it.first<<'\n';
        rsp[it.first]=max(rsp[it.first],prv);
        for (auto it2 : it.second)
        {
            //cout<<it2<<' ';
            if (fin[it2]!=it.first)
                rsp[fin[it2]]=max(rsp[fin[it2]],rsp[it.first]+fin[it2]-it.first);
        }
        prv=rsp[it.first];
        //cout<<'\n';
    }
    for (auto it : rsp)
        mx=max(mx,it.second);
    g<<mx;
}