Cod sursa(job #2513332)

Utilizator DariusDCDarius Capolna DariusDC Data 22 decembrie 2019 21:50:50
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

int n, tmax;
int dp[100005];
int st, dr;

struct concert
{
    int a, b;
}c[100005];

bool cmp(concert a, concert b)
{
    if (a.b == b.b)
        return a.a < b.a;
    return a.b < b.b;
}

inline int cb(int x)
{
    int ans = 0;
    while (st <= dr)
    {
        int mij = (st+dr)/2;
        if (c[mij].b <= x)
        {
            ans = mij;
            st = mij+1;
        }
        else
            dr = mij - 1;
    }
    return ans;
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> c[i].a >> c[i].b, tmax = max(tmax, c[i].b);
    sort(c + 1, c + n + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
        int x = c[i].a;
        int y = c[i].b;
        int timp = y - x;
        st = 1;
        dr = i;
        int p = cb(x);
        dp[i] = max(dp[i-1], dp[p] + timp);
    }
    fout << dp[n];
    return 0;
}