Cod sursa(job #2227848)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 2 august 2018 00:14:39
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 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);

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

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