Cod sursa(job #1883082)

Utilizator mihai.alphamihai craciun mihai.alpha Data 17 februarie 2017 18:24:07
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("heavymetal.in");
ofstream g("heavymetal.out");

#define MAX 100001
#define fi first
#define se second

int N;
pair <int, int> ab[MAX];

int dp[MAX];

inline int caut(int val)  {
    int pas = 1 << 22;
    int r = 0;
    while(pas)  {
        if(r + pas <= N && ab[r + pas].se <= val)
            r += pas;
        pas >>= 1;
    }
    return r;
}

bool cmp(pair <int, int>a, pair <int, int>b)  {
    return a.se < b.se;
}

int main()  {
    f >> N;
    for(int i = 1;i <= N;i++)
        f >> ab[i].fi >> ab[i].se;
    sort(ab + 1, ab + N + 1, cmp);
    for(int i = 1;i <= N;i++)  {
        int ct = caut(ab[i].fi);
        dp[i] = max(dp[i - 1], dp[ct] + (ab[i].se - ab[i].fi));
    }
    g << dp[N];
    f.close(), g.close();
    return 0;
}