Pagini recente » Rating cont de incercari (Razvan_Andrei) | Cod sursa (job #1696087) | Cod sursa (job #287514) | Cod sursa (job #1544197) | Cod sursa (job #2180764)
#include<bits/stdc++.h>
using namespace std;
const int N=100020;
struct pod{
int x, y, c;
}a[N];
int p[N],q[N],l=1, dp[N], mx;
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;
p[i]=m;
q[m]=a[i].y;
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;
p[1]=1;
q[1]=a[1].x;
for(int i=2;i<=n;i++){
caut(i);
}
g<<mx;
}