Pagini recente » Cod sursa (job #1240234) | Cod sursa (job #2157916) | Cod sursa (job #2772682) | Cod sursa (job #1785710) | Cod sursa (job #2511578)
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#include <map>
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pll pair<long,long>
#define pdd pair<double,double>
//#define first f
//#define second s
#define INF 1e9
#define MOD 1e9+7
using namespace std;
int N,i,j,k,ans;
int dp[100010];
vector<pair<int,int> > v(100010);
int cautare_binara_1(int x,int l,int r)
{
int mij,pos=-1;
while(l<=r)
{
mij=(l+r)/2;
if (v[mij].second<=x)
{
pos=mij;
l=mij+1;
}
else
{
r=mij-1;
}
}
return pos;
}
bool cmp(const pair<int,int> & a,const pair<int,int> & b)
{
if(a.second!=b.second)
return (a.second<b.second);
else
return (a.first<b.first);
}
//dp[i] - cel mai bun cost din primele i spectacole sortate dupa capatul din dreata, in care il scoatem si pe i
//dp[i] = max(dp[i-1],y[i]-x[i]+dp[j]) unde j e cel mai mare index astfel incat y[index] mai mic decat x[i]
int main()
{
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
fin>>N;
v = vector<pair<int, int>> (N + 1);
v[0].first=-1;
v[0].second=-1;
for(i=1;i<=N;i++)
{
fin>>v[i].first>>v[i].second;
}
sort(v.begin(),v.end(),cmp);
for(i=1;i<=N;i++)
{
k=cautare_binara_1(v[i].first,0,i-1);
dp[i]=max(dp[i-1],v[i].second-v[i].first+dp[k]);
}
// for(i=0;i<=N;i++)
// {
// cout<<dp[i]<<' ';
// }
fout<<dp[N];
fin.close();
fout.close();
return 0;
}