oj.uz

Submission #18022

# Submission time Handle Problem Language Result Execution time Memory
18022 2016-01-18T11:31:09 Z gs13068 매트 (KOI15_mat) C++
100 / 100
 301 ms 88248 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 88248 KB Output is correct
2 Correct 0 ms 88248 KB Output is correct
3 Correct 0 ms 88248 KB Output is correct
4 Correct 0 ms 88248 KB Output is correct
5 Correct 0 ms 88248 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 88248 KB Output is correct
2 Correct 0 ms 88248 KB Output is correct
3 Correct 0 ms 88248 KB Output is correct
4 Correct 0 ms 88248 KB Output is correct
5 Correct 0 ms 88248 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 88248 KB Output is correct
2 Correct 0 ms 88248 KB Output is correct
3 Correct 2 ms 88248 KB Output is correct
4 Correct 2 ms 88248 KB Output is correct
5 Correct 2 ms 88248 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 88248 KB Output is correct
2 Correct 189 ms 88248 KB Output is correct
3 Correct 188 ms 88248 KB Output is correct
4 Correct 166 ms 88248 KB Output is correct
5 Correct 116 ms 88248 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 88248 KB Output is correct
2 Correct 301 ms 88248 KB Output is correct
3 Correct 278 ms 88248 KB Output is correct
4 Correct 270 ms 88248 KB Output is correct
5 Correct 179 ms 88248 KB Output is correct
6 Correct 161 ms 88248 KB Output is correct
7 Correct 278 ms 88248 KB Output is correct
8 Correct 169 ms 88248 KB Output is correct
9 Correct 114 ms 88248 KB Output is correct
10 Correct 178 ms 88248 KB Output is correct