Pagini recente » Cod sursa (job #1203367) | Cod sursa (job #3178091) | Cod sursa (job #1510914) | Cod sursa (job #2679920) | Cod sursa (job #2180766)
#include<bits/stdc++.h>
using namespace std;
const int N=100020;
struct pod{
int x, y, c;
}a[N];
int q[N],l=1, dp[N], mx, ord[N];
void caut(int i){
int st=1, dr=l, x=a[i].x, m=(st+dr)/2;
while(st<dr){
if(q[m]<x)st=m+1; else dr=m;
m=(st+dr)/2;
}
if(q[m]<=x)m++;
if(m==l+1)l++;
if(dp[m-1]+a[i].c>dp[m])dp[m]=dp[m-1]+a[i].c;
if(q[m]==x && a[i].c<a[ord[m]].c)return;
q[m]=a[i].y;
ord[m]=i;
if(dp[m]>mx)mx=dp[m];
}
int cmp(pod b, pod c){
if(b.y==c.y)return b.x<c.x;
return (b.y<c.y);
}
int main(){
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int n;
f>>n;
for(int i=1;i<=n;i++){
f>>a[i].x>>a[i].y;
a[i].c=a[i].y-a[i].x;
}
sort(a+1,a+1+n, cmp);
mx=dp[1]=a[1].c;
ord[1]=1;
q[1]=a[1].x;
for(int i=2;i<=n;i++){
caut(i);
}
g<<mx;
}