Pagini recente » Cod sursa (job #2621137) | Cod sursa (job #1520427) | Cod sursa (job #565819) | Cod sursa (job #2079959) | Cod sursa (job #2336573)
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
bool cmp(const pii &a, const pii &b)
{
return a.second < b.second;
}
int main()
{
ifstream in("heavymetal.in");
int n;
in >> n;
vector<pii> v(n);
for(auto &p:v)
in >> p.first >> p.second;
in.close();
int rasp = 0;
sort(v.begin(), v.end(), cmp);
set<pii> dp; //.first = capat dreapta, .second = val
for(auto &p:v)
{
int x = p.second - p.first;
auto it = dp.upper_bound(make_pair(p.first, 0));
if(it != dp.begin())
{
it--;
x = max(x, x - (*it).second);
}
dp.insert(make_pair(p.second, -x));
rasp = max(rasp, x);
}
ofstream out("heavymetal.out");
out << rasp;
out.close();
return 0;
}