Submission #305111

#	Time	Username	Problem	Language	Result	Execution time	Memory
305111		ansol4328	매트 (KOI15_mat)	C++14	100 / 100	274 ms	62200 KiB

mat

#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];
vector<int> lst[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> idx;
    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);
        idx.push_back(m[i].s);
        idx.push_back(m[i].e);
    }
    sort(m+1,m+1+n,cmp);
    sort(idx.begin(),idx.end());
    idx.erase(unique(idx.begin(),idx.end()),idx.end());
    for(int i=1 ; i<=n ; i++){
        m[i].s=lower_bound(idx.begin(),idx.end(),m[i].s)-idx.begin()+1;
        m[i].e=lower_bound(idx.begin(),idx.end(),m[i].e)-idx.begin()+1;
        lst[m[i].s].push_back(i);
    }
    m[0].t=-1, m[0].s=m[0].e=1;
    int sz=idx.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]=max(D[i][j],R[j]+m[i].v);
                R[m[i].e]=max(R[m[i].e],D[i][j]);
            }
            D[i][j]=max(D[i][j],D[i][j-1]);
            if(j<m[i].e){
                for(int k : lst[j]){
                    if(m[k].t!=m[i].t && !cross(m[k],m[i])){
                        if(m[k].e<=m[i].e){
                            D[i][m[k].e]=max(D[i][m[k].e],D[i][j]+m[k].v);
                            R[m[i].e]=max(R[m[i].e],D[i][m[k].e]);
                        }
                        else{
                            D[k][m[i].e]=max(D[k][m[i].e],D[i][j]+m[k].v);
                            R[m[k].e]=max(R[m[k].e],D[k][m[i].e]);
                        }
                    }
                }
            }
            R[j]=max(R[j-1],R[j]);
            ans=max(ans,R[j]);
        }
    }
    printf("%d",ans);
    return 0;
}

Compilation message (stderr)

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

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