Cod sursa(job #2303019)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 15 decembrie 2018 13:45:12
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef long long ll;
typedef long double ld;

const string file = "heavymetal";
const ll INF = 9223372036854775807ll;
const int inf = 2147483647;

struct ev{
    int x, y;
    bool operator<(const ev & obj)const{
        if(y != obj.y)
            return y < obj.y;
        return x < obj.x;
    }
};

ev v[100005];
int n, mx[100005];

int main()
{
    ifstream fin (file+".in");
    ofstream fout (file+".out");
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i].x >> v[i].y;
    sort(v+1, v+n+1);
    mx[1] = v[1].y-v[1].x;
    for (int i = 2; i <= n; ++i){
        int st = 1, dr = i-1, m, ans = 0;
        for (m = (st+dr)/2; st <= dr; m = (st+dr)/2)
            if(v[m].y <= v[i].x){
                ans = m;
                st = m+1;
            }else dr = m-1;
        mx[i] = max(mx[i-1], mx[ans]+v[i].y-v[i].x);
    }
    fout << mx[n] << "\n";
    return 0;
}