Cod sursa(job #2451712)

Utilizator Senth30Denis-Florin Cringanu Senth30 Data 27 august 2019 20:39:37
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <bits/stdc++.h>
#define MAX 131072

using namespace std;
const int NMAX = 100020;

FILE *IN;

int N, poz;
int dp[NMAX];
vector <pair <int, int> > V;

int pos, sign;
char f[MAX];

inline void Read(int &nr){
    sign = 0;
    nr = 0;
    while(f[pos] < '0' || f[pos] > '9'){
        if(f[pos] == '-') sign=1;
        pos++;
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    while(f[pos] >= '0' && f[pos] <= '9'){
        nr = 10 * nr + f[pos++] - '0';
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    if(sign) nr =- nr;
}

int read(){
    Read(N);
    int a, b;
    V.push_back(make_pair(0, 0));
    for(int i = 1; i <= N; i++){
        Read(a); Read(b);
        V.push_back(make_pair(a, b));
    }
}

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

int binsearch(int x, int st, int nd){
    int mid, last = 0;
    while(st <= nd){
        mid = (st + nd) / 2;
        if(V[mid].second <= x){
            last = mid;
            st = mid + 1;
        } else nd = mid - 1;
    }

    return last;
}

int main(){

    IN = fopen("heavymetal.in", "r");
    freopen("heavymetal.out", "w", stdout);

    read();
    sort(V.begin(), V.end(), cmp);

    for(int i = 1; i <= N; i++){
        if(V[i].first >= V[1].second)
            pos = binsearch(V[i].first, 1, i);
        else pos = 0;
        dp[i] = max(dp[i - 1], dp[pos] + V[i].second - V[i].first);
    }

    printf("%d", dp[N]);

    return 0;
}