oj.uz

Submission #305111

# Submission time Handle Problem Language Result Execution time Memory
305111 2020-09-22T15:25:53 Z ansol4328 매트 (KOI15_mat) C++14
100 / 100
 274 ms 62200 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];
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

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.0 / 8.0

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

Subtask #2
13.0 / 13.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 57976 KB Output is correct
2 Correct 149 ms 57720 KB Output is correct
3 Correct 138 ms 58104 KB Output is correct
4 Correct 139 ms 57976 KB Output is correct
5 Correct 20 ms 12928 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 62200 KB Output is correct
2 Correct 268 ms 58104 KB Output is correct
3 Correct 274 ms 58104 KB Output is correct
4 Correct 267 ms 57848 KB Output is correct
5 Correct 176 ms 34588 KB Output is correct
6 Correct 119 ms 47060 KB Output is correct
7 Correct 221 ms 43896 KB Output is correct
8 Correct 88 ms 13560 KB Output is correct
9 Correct 59 ms 12852 KB Output is correct
10 Correct 89 ms 13560 KB Output is correct