i use a lecture hall algo
here it is:
#include <iostream.h>

struct Putnik
{
    int s;
    int f;
    int b;
    int br;
};

int min(int x,int y)
{
    return x<y?x:y;
}

void merge(Putnik *a,int f,int s,int n)
{

    int i,j,k;
    Putnik *b;
    b=new Putnik[n-f];
    k=0;
    i=f;
    j=s;
    while(i<s && j<n)
    {
        if (a[i].f<a[j].f) b[k++]=a[i++];
        else b[k++]=a[j++];
    }
    while(i<s) b[k++]=a[i++];
    while(j<n) b[k++]=a[j++];
    for(i=0;i<k;i++)
        a[i+f]=b[i];
    delete [] b;

}

main()
{
    int n,k,m,p,i,j,z,l,mn;
    Putnik pt;
    Putnik *a;
    cin >>n>>m>>k>>p;
    a=new Putnik[k];
    for(i=0;i<k;i++)
    {
        cin>>a[i].s;
        cin>>a[i].f;
        a[i].b=1;
        a[i].br=i+1;
    }

    for(i=1;i<k;i*=2)
        for(j=0;j<k;j+=2*i)
            if (j+i<k) merge(a,j,j+i,min(k,j+2*i));


    z=k;
    for(i=0;i<m && z;i++)
    {
        l=0;
        while(a[l].b==0) l++;
        pt=a[l];
        a[l].b=0;
        z--;
        for(j=l+1;j<k;j++)
            if (a[j].b && a[j].s>=pt.f)
            {
                z--;
                a[j].b=0;
                pt=a[j];
            }

    }

    mn=(k-z)*p;
    cout<<mn<<"\n";
    for(i=0;i<k;i++)
        if (a[i].b==0) cout<<a[i].br<<" ";

    delete [] a;






}

and get wa# 5
i dont see a bug here plz help me
some tests would be nise also

Edited by author 10.09.2008 21:58