Pagini recente » Cod sursa (job #1439667) | Cod sursa (job #2896293) | Cod sursa (job #1089856) | Borderou de evaluare (job #2388892) | Cod sursa (job #2469174)
#include<bits/stdc++.h>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
const int NAX = 1e5 + 5;
vector<pair<int,int> >v;
int n, dp[ NAX ];
int cb(int i)
{
int st = 0, dr = i - 1, mij, sol = 0;
while( st <= dr )
{
mij = st + ( dr - st )/2;
if( v[ mij ].second <= v[ i ].first )
{
sol = mij;
st = mij + 1;
}
else
dr = mij - 1;
}
return sol;
}
bool cmp(pair<int, int> a, pair<int, int> b)
{
}
int main()
{
f >> n;
for(int x, y, i = 1 ; i <= n ; ++i)
{
f >> x >> y;
v.push_back({x, y});
}
sort(v.begin(), v.end());
dp[ 0 ] = abs( v[ 0 ].first - v[ 0 ].second );
for(int i = 1 ; i < n ; ++i)
{
int poz = cb(i);
dp[ i ] = max( dp[ i - 1 ], dp[ poz ] + abs( v[ i ].first - v[ i ].second ));
}
g << dp[ n - 1 ];
}