Pagini recente » Cod sursa (job #1006786) | Cod sursa (job #686356) | Cod sursa (job #2192758) | Cod sursa (job #1718391) | Cod sursa (job #1099513)
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
struct formatie {int start;int sfarsit;};
formatie trupa[100010];
int n,dp[100010];
bool cmp(formatie A,formatie B) {
return A.sfarsit<B.sfarsit;
}
void citire() {
ifstream in("heavymetal.in");
int i;
in>>n;
for(i=1;i<=n;i++)
in>>trupa[i].start>>trupa[i].sfarsit;
in.close();
}
int cautbin(int lol) {
int st,dr,m;
st=0;
dr=lol;
while(st<=dr) {
m=(st+dr)/2;
if(trupa[m].sfarsit>trupa[lol].start)
dr=m-1;
else
st=m+1;
}
m=(st+dr)/2;
return m;
}
void solve() {
int i,maxim,a,poz;
sort(trupa+1,trupa+n+1,cmp);
dp[1]=trupa[1].sfarsit-trupa[1].start;
maxim=dp[1];
for(i=2;i<=n;i++) {
poz=cautbin(i);
a=trupa[i].sfarsit-trupa[i].start;
if(dp[poz]+a>maxim) {
maxim=dp[poz]+a;
dp[i]=dp[poz]+a;
}
else
dp[i]=maxim;
}
}
void afisare() {
ofstream out("heavymetal.out");
int i;
out<<dp[n];
out.close();
}
int main () {
citire();
solve();
afisare();
return 0;
}