Cod sursa(job #2050027)

Utilizator crion1999Anitei cristi crion1999 Data 27 octombrie 2017 21:50:51
Problema Heavy metal Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>
#define NMAX 100005
#define INF 0x3f3f3f3f
using namespace std;

ifstream fi("heavymetal.in"); void Input();
ofstream fo("heavymetal.out"); void Output();

struct dur 
{
    int start, end;
    bool operator <(const dur &other) const {return end < other.end;}
};

dur bands[NMAX];
long long dp[NMAX];
int N;

int binarySearch(int val) 
{
    int step = INF;
    int pos = 0;
    while (step != 0) 
    {
        if (pos + step <= N && bands[pos + step].end <= val) 
        {
            pos += step;
        }
        step /= 2;
    }
    return pos;
}

int main()
{
    Input();
    sort(bands + 1, bands + N + 1);
    dp[1] = bands[1].end - bands[1].start;
    for (int i = 2; i <= N; ++i) 
    {
        int before = binarySearch(bands[i].start);
        dp[i] = max( (bands[i].end - bands[i].start) + dp[before], dp[i - 1]);
    }
    Output();
}

void Input()
{
    fi>>N;
    
    for (int i = 1; i <= N; ++i) 
    {
        fi>>bands[i].start>>bands[i].end;
    }
}
void Output()
{
    fo<<dp[N];
}