记录编号	12632	评测结果	AAAAAAAAAA
题目名称	[POI 1997] 阶梯教室设备利用	最终得分	100
用户昵称	yanzheng	是否通过	通过
代码语言	C	运行时间	1.845 s
提交时间	2009-09-16 17:43:10	内存使用	0.31 MiB

#include <stdio.h>

int s[10001],e[10001];

int maxv(int a,int b)
{
    if(a>b) return a;
    return b;
}

void qs(int l,int r)
{
    if(l<r)
    {
        int tmp,m=l-1,k;
        for(k=l;k<r;k++)
        {
            if(e[k]>e[r])
            {
                m++;
                tmp=e[k];
                e[k]=e[m];
                e[m]=tmp;
                tmp=s[k];
                s[k]=s[m];
                s[m]=tmp;
            }
        }
        m++;
        tmp=e[r];
        e[r]=e[m];
        e[m]=tmp;
        tmp=s[r];
        s[r]=s[m];
        s[m]=tmp;
        qs(l,m-1);
        qs(m+1,r);
    }
}

int main()
{
    FILE *in,*out;
    in=fopen("rez.in","r");
    out=fopen("rez.out","w");
    int i,j,k,n,max=0,f[10001];

    fscanf(in,"%d",&n);
    for(k=0;k<n;k++)
        fscanf(in,"%d%d",&s[k],&e[k]);

    qs(0,n-1);

    for(k=n-1;k>=0;k--)
    {
        f[k]=0;
        for(i=k+1;i<n;i++)
        {
            if(e[i]<=s[k] && f[i]>f[k])
            {
                f[k]=f[i];
            }
        }
        f[k]+=e[k]-s[k];
        if(f[k]>max) max=f[k];
    }

    fprintf(out,"%d\n",max);

    return 0;
}