Pagini recente » Autentificare | Cod sursa (job #993868) | Istoria paginii runda/here_we_go_oni_11-12/clasament | Monitorul de evaluare | Cod sursa (job #1574993)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int Nmax = 100005;
int N, intMax; // intMax = interval maxim
pair<int,int> Con[Nmax];
int best[Nmax];
void read()
{
ifstream f("heavymetal.in");
f >> N;
for(int i = 1; i <= N; i ++)
{
f >> Con[i].first;
f >> Con[i].second;
}
f.close();
}
bool compareByFinish(pair<int,int> x, pair<int,int> y)
{
return(x.second < y.second);
}
void solve()
{
sort(Con+1,Con+N+1,compareByFinish);
int st, dr, m, poz;
for(int i = 1; i <= N; i ++)
{
st = 1, dr = i-1;
poz = 0;
while(st <= dr)
{
m = (st+dr)>>1;
if(Con[m].second <= Con[i].first)
{
poz = m;
st = m+1;
}
else
{
dr = m-1;
}
}
best[i] = max(best[i-1], best[poz] + Con[i].second-Con[i].first);
}
}
void print()
{
ofstream g("heavymetal.out");
g << best[N];
g.close();
}
int main()
{
read();
solve();
print();
return 0;
}