Cod sursa(job #2227850)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 2 august 2018 00:22:21
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <algorithm>
#include <iostream>

using namespace std;

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

const int Dim = 100001;
pair < int, int > A[Dim];

int n,ma,D[Dim];
int CB(int val, int dr);
bool cmp(pair<int, int > a, pair<int,int>b);


int main(){ 
	
	fin >> n;
	for ( int i = 1; i <= n; ++i)
			fin >> A[i].first >> A[i].second;
	sort(A+1,A+1+n,cmp);
	for ( int i = 1; i <= n; ++i) {
		D[i] = A[i].second - A[i].first;
		D[i] += D[CB(A[i].first,i-1)];
		ma = max(ma,D[i]);
	}
	fout << ma;	
}

bool cmp(pair<int, int > a, pair<int,int>b) {
	
	return a.second < b.second;
}

int CB(int val, int dr) {
	
	int st = 1,mj,sol = 0;
	while ( st <= dr ){ 
		mj = ( st + dr )/2;
		if ( A[mj].second > val) 
			dr = mj - 1;
		else {
			sol = mj;
			st = mj + 1;
			}
	}
	return sol;
}