Pagini recente » Cod sursa (job #3310409) | Cod sursa (job #3305752) | Cod sursa (job #336041) | Cod sursa (job #3306129) | Cod sursa (job #3313481)
#include<fstream>
#include<vector>
#include<algorithm>
#define ll long long
std::ifstream fin("heavymetal.in");
std::ofstream fout("heavymetal.out");
std::vector<std::pair<int, int>>v;
int n;
void read()
{
fin>>n;
v.emplace_back(0, 0);
for(int i=1; i<=n; ++i)
{
int l, r;
fin>>l>>r;
v.emplace_back(l, r);
}
std::sort(v.begin(), v.end(), [](std::pair<int, int>a, std::pair<int, int>b){
return a.second<b.second;
});
}
inline int find_left(int idx)
{
int lg;
for(lg=1; lg<n; lg<<=1);
int pos=0;
for(int d=lg; d; d>>=1)
{
if(pos+d<=n && v[pos+d].second<=v[idx].first)
pos+=d;
}
return pos;
}
void solve()
{
std::vector<ll>dp(n+5);//solutia care include intervalul i
std::vector<ll>best(n+5);//solutia cea mai buna pana la i
dp[0]=best[0]=0;
for(int i=1; i<=n; ++i)
{
int idx=find_left(i);
dp[i]=best[idx]+v[i].second-v[i].first;
best[i]=std::max(dp[i], best[i-1]);
}
fout<<best[n];
}
int main()
{
read();
solve();
return 0;
}