oj.uz

Submission #298096

# Submission time Handle Problem Language Result Execution time Memory
298096 2020-09-12T11:44:28 Z ansol4328 매트 (KOI15_mat) C++14
32 / 100
 282 ms 71160 KB 
#include<bits/stdc++.h>

using namespace std;

struct A{
    int t, s, e, h, v;
    A() {}
};

int n, w;
A m[3005];
int D[3005][6005], R[6005];

bool cmp(const A &lhs, const A &rhs){
    return lhs.e!=rhs.e ? lhs.e<rhs.e : lhs.s<rhs.s;
}

bool cross(const A &lhs, const A &rhs){
    if(lhs.e<=rhs.s || lhs.s>=rhs.e) return false;
    if(lhs.t!=rhs.t && lhs.h+rhs.h<=w) return false;
    return true;
}

int main()
{
    vector<int> lst;
    scanf("%d %d",&n,&w);
    for(int i=1 ; i<=n ; i++){
        scanf("%d %d %d %d %d",&m[i].t,&m[i].s,&m[i].e,&m[i].h,&m[i].v);
        lst.push_back(m[i].s);
        lst.push_back(m[i].e);
    }
    sort(m+1,m+1+n,cmp);
    sort(lst.begin(),lst.end());
    lst.erase(unique(lst.begin(),lst.end()),lst.end());
    for(int i=1 ; i<=n ; i++){
        m[i].s=lower_bound(lst.begin(),lst.end(),m[i].s)-lst.begin()+1;
        m[i].e=lower_bound(lst.begin(),lst.end(),m[i].e)-lst.begin()+1;
    }
    m[0].t=-1, m[0].s=m[0].e=1;
    int sz=lst.size(), ans=0;
    for(int i=1 ; i<=n ; i++){
        for(int j=1 ; j<=sz ; j++){
            if(j>m[i].e) break;
            if(j<=m[i].s){
                D[i][j]=R[j]+m[i].v;
                R[m[i].e]=max(R[m[i].e],D[i][j]);
            }
            if(j==m[i].e){
                for(int k=i-1 ; k>=0 ; k--){
                    if(m[i].t!=m[k].t && !cross(m[i],m[k])){
                        R[j]=max(R[j],D[k][m[i].s]+m[i].v);
                        D[i][m[k].e]=max(D[i][m[k].e],D[k][m[i].s]+m[i].v);
                    }
                }
            }
            R[j]=max(R[j-1],R[j]);
            ans=max(ans,R[j]);
        }
        for(int j=1 ; j<=sz ; j++) D[i][j]=max(D[i][j-1],D[i][j]);
    }
    printf("%d",ans);
    return 0;
}

Compilation message

mat.cpp: In function 'int main()':
mat.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |     scanf("%d %d",&n,&w);
      |     ~~~~~^~~~~~~~~~~~~~~
mat.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |         scanf("%d %d %d %d %d",&m[i].t,&m[i].s,&m[i].e,&m[i].h,&m[i].v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
13.0 / 13.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 71036 KB Output is correct
2 Correct 171 ms 71032 KB Output is correct
3 Correct 175 ms 71160 KB Output is correct
4 Correct 177 ms 71032 KB Output is correct
5 Correct 16 ms 12800 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 71092 KB Output is correct
2 Incorrect 282 ms 71160 KB Output isn't correct
3 Halted 0 ms 0 KB -