Pagini recente » Cod sursa (job #1902293) | Cod sursa (job #1264188) | Cod sursa (job #1713355) | Cod sursa (job #997988) | Cod sursa (job #2469200)
#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, mij, sol = 0;
while( st < dr )
{
mij = (st + dr + 1)/2;
if( v[ mij ].second <= v[ i ].first )
{
st = mij;
}
else
dr = mij - 1;
}
return st;
}
bool cmp(pair<int, int> a, pair<int, int>b)
{
return a.second < b.second;
}
int main()
{
f >> n;
v.push_back({0,0});
for(int x, y, i = 1 ; i <= n ; ++i)
{
f >> x >> y;
v.push_back({x, y});
}
sort(v.begin() + 1, v.end(), cmp);
dp[ 1 ] = abs( v[ 1 ].first - v[ 1 ].second );
for(int i = 2 ; 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 ];
}