Pagini recente » Cod sursa (job #2272301) | Cod sursa (job #608010) | Cod sursa (job #2381807) | Cod sursa (job #3265675) | Cod sursa (job #347267)
Cod sursa(job #347267)
#include <cstdio>
#include <algorithm>
#define N 100000
using namespace std;
struct bands
{
int li,ls;
} A[N];
int ind[N],timp[N],B[N];
//long long B[N];
bool cmp(int i, int j)
{
/*if (A[i].li==A[j].li) return A[i].ls<A[j].ls;
else return A[i].li<A[j].li;*/
return A[i].ls<A[j].ls;
}
int main()
{
int n,i,j,best,best_total=0;
//long long best, best_total=0;
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for (i=1; i<=n; i++) scanf("%d%d",&A[i].li,&A[i].ls), ind[i]=i, timp[i]=A[i].ls-A[i].li;
sort(ind+1,ind+n+1,cmp);
B[1]=timp[ind[1]];
best_total=timp[ind[1]];
for (i=2; i<=n; i++)
{
best=0;
for (j=1; j<i; j++)
if (A[ind[i]].li>=A[ind[j]].ls && A[ind[i]].ls>A[ind[j]].ls && B[j]+timp[ind[i]]>best)
best=B[j]+timp[ind[i]];
if (best>best_total) best_total=best;
B[i]=best;
}
printf("%d",best_total);
//for (i=1; i<=n; i++) printf("%d %d %d\n",A[ind[i]].li,A[ind[i]].ls,timp[ind[i]]);
return 0;
}