Cod sursa(job #1901117)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 3 martie 2017 19:08:42
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <algorithm>
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int maxn = 100005;
int dp1[1005][1005]; /// dp[i][j] = numarul maxim de minute din primele i timp maxim j
int dp[maxn];
pair <int, int> v[maxn];

int p;
int cautbin(int x)
{
    int st = 1;
    int dr = p - 1;
    int ret = 0;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(v[mij].second <= x)
        {
            st = mij + 1;
            ret = mij;
        }
        else
            dr = mij - 1;
    }
    return ret;
}

inline bool cmp(pair <int, int> a, pair <int, int> b)
{
    if(a.second != b.second)
        return a.second < b.second;
    return a.first < b.first;
}

int main()
{
    int n;
    in >> n;
    for(int i = 1; i <= n; i++)
        in >> v[i].first >> v[i].second;
    sort(v + 1, v + n + 1);
    //if(n <= 1000)
        //brut();
    for(int i = 1; i <= n; i++)
    {
        p = i;
        int durata = v[i].second - v[i].first;
        dp[i] = dp[i - 1];
        dp[i] = max(dp[i], dp[cautbin(v[i].first)] + durata);
    }
    out << dp[n];
    return 0;
}