Pagini recente » Cod sursa (job #1478068) | Cod sursa (job #1189351) | Cod sursa (job #3256395) | Cod sursa (job #3281568) | Cod sursa (job #149828)
Cod sursa(job #149828)
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100001
struct wtf
{
int s,e,v;
};
wtf V[MAXN];
int v[MAXN],n;
int cmp(const void *a, const void *b)
{
wtf x=*(wtf*)a,y=*(wtf*)b;
return x.e-y.e;
}
int ffs(int p)
{
int k,i;
k=V[p-1].v;
if (v[p-1]>k)
k=v[p-1];
for (i=p-1; i>0; i--)
if (V[i-1].e<=V[p-1].s)
{
if (k<v[i]+V[p-1].v)
k=v[i]+V[p-1].v;
i=0;
}
return k;
}
int main()
{
FILE *in = fopen("heavymetal.in","r");
FILE *out = fopen("heavymetal.out","w");
int i;
fscanf(in,"%d",&n);
for (i=0; i<n; i++)
{
fscanf(in,"%d%d",&V[i].s,&V[i].e);
V[i].v=V[i].e-V[i].s;
}
qsort(V,n,sizeof(V[0]),cmp);
v[0]=0; v[1]=V[0].v;
for (i=2; i<=n; i++)
v[i]=ffs(i);
fprintf(out,"%d\n",v[n]);
fclose(in);
fclose(out);
return 0;
}