Cod sursa(job #2041848)

Utilizator dragos231456Neghina Dragos dragos231456 Data 17 octombrie 2017 20:24:43
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct {
    int x,y;
}interv[100005];
int dp[200005],n,m,k,v[200005],fr[200005];
vector<int> inv[200005];
map<int,int> mp;
int main()
{
    f>>n; m=2*n;
    for(int i=1;i<=n;++i)
    {
        f>>interv[i].x>>interv[i].y;
        v[2*i-1]=interv[i].x;
        v[2*i]=interv[i].y;
    }
    sort(v+1,v+m+1);
    for(int i=1;i<=m;++i)
    {
        if(v[i]!=v[i-1])
        {
            ++k;
            mp[v[i]]=k;
            fr[k]=v[i];
        }
    }
    for(int i=1;i<=n;++i)
    {
        interv[i].x=mp[interv[i].x];
        interv[i].y=mp[interv[i].y];
        inv[interv[i].y].push_back(interv[i].x);
    }
    for(int i=1;i<=m;++i)
    {
        dp[i]=dp[i-1];
        for(int j=0;j<inv[i].size();++j)
        {
            dp[i]=max(dp[i],dp[inv[i][j]]+fr[i]-fr[inv[i][j]]);
        }
    }
    g<<dp[m];
    return 0;
}