Submission #18022

#	Time	Username	Problem	Language	Result	Execution time	Memory
18022		gs13068	매트 (KOI15_mat)	C++98	100 / 100	301 ms	88248 KiB

mat

#include<cstdio>
#include<vector>
#include<algorithm>
 
struct mat
{
    int w,l,r,h,c;
} a[3333];
 
bool operator <(const mat &a,const mat &b)
{
    if(a.l!=b.l)return a.l<b.l;
    if(a.r!=b.r)return a.r<b.r;
    if(a.w!=b.w)return a.w<b.w;
    if(a.h!=b.h)return a.h<b.h;
    return a.c<b.c;
}
 
int t[6666];
int d[3333][6666];
std::vector<int> b[6666];
 
int m;
 
int crs(const mat &a,const mat &b)
{
    return a.l<b.r&&b.l<a.r&&(a.w==b.w||a.h+b.h>m);
}
 
int main()
{
    int i,j,k,n,res=0;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
    {
        scanf("%d%d%d%d%d",&a[i].w,&a[i].l,&a[i].r,&a[i].h,&a[i].c);
        t[i]=a[i].l;
        t[i+n]=a[i].r;
    }
    std::sort(a,a+n);
    std::sort(t,t+n+n);
    for(i=0;i<n;i++)
    {
        a[i].l=std::upper_bound(t,t+n+n,a[i].l)-t;
        a[i].r=std::upper_bound(t,t+n+n,a[i].r)-t;
        b[a[i].l].push_back(i);
    }
    for(i=0;i<n;i++)
    {
        d[i][0]=a[i].c;
        for(j=0;j<n+n;j++)
        {
            d[i][j+1]=std::max(d[i][j+1],d[i][j]);
            for(k=0;k<b[j].size();k++)if(!crs(a[i],a[b[j][k]]))
            {
                if(a[i].r<a[b[j][k]].r)d[b[j][k]][a[i].r]=std::max(d[b[j][k]][a[i].r],d[i][j]+a[b[j][k]].c);
                else d[i][a[b[j][k]].r]=std::max(d[i][a[b[j][k]].r],d[i][j]+a[b[j][k]].c);
            }
        }
        res=std::max(res,d[i][n+n]);
    }
    printf("%d\n",res);
}

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 11 / 11
• Subtask 5: 43 / 43