Cod sursa(job #1521463)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 10 noiembrie 2015 15:10:31
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>

#define INF (1 << 30)
#define LLINF (1LL << 62)
#define mod 666013

using namespace std;

struct formatie
{
    int st, dr, val;
}v[100005];

int n, i, j, x, mx, sol;
int dp[200005];

vector <int> a;
unordered_map <int, int> mp;

bool cmp(formatie a, formatie b)
{
    if(a.st == b.st)
        return a.dr < b.dr;
    return a.st < b.st;
}

int main()
{
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);

    scanf("%d", &n);
    for(i = 1; i <= n; i++)
    {
        scanf("%d%d", &v[i].st, &v[i].dr);
        a.push_back(v[i].st);
        a.push_back(v[i].dr);
        v[i].val = v[i].dr - v[i].st;
    }

    sort(a.begin(), a.end());

    x = 0;
    for(i = 0; i < a.size(); i++)
    {
        if(mp.count(a[i]))
            continue;
        mp[ a[i] ] = ++x;
    }

    for(i = 1; i <= n; i++)
    {
        v[i].st = mp[ v[i].st ];
        v[i].dr = mp[ v[i].dr ];
    }

    sort(v + 1, v + n + 1, cmp);

    mx = 0;
    j = 0;
    for(i = 1; i <= n; i++)
    {
        while(j < v[i].st)
        {
            j++;
            mx = max(mx, dp[j]);
        }

        dp[ v[i].dr ] = max(dp[ v[i].dr ], mx + v[i].val);
        sol = max(sol, dp[ v[i].dr ]);
    }

    printf("%d", sol);
    return 0;
}