Submission #71269

#	Time	Username	Problem	Language	Result	Execution time	Memory
71269		3zp	매트 (KOI15_mat)	C++14	57 / 100	1088 ms	12924 KiB

mat

#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
vector<pair<pii,pii> > a, b;
int dp[3009][3009], ans;
int al[3009], ar[3009], ah[3009], ac[3009];
int bl[3009], br[3009], bh[3009], bc[3009];
main(){
    a . push_back ({{-1, -1}, {1 , 1}});
    b . push_back ({{-1, -1}, {1 , 1}});
    int n, w;
    cin >> n >> w;
    for(int i = 0; i < n; i++){
        int p, l, r, h, c;
        cin >> p >> l >> r >> h >> c;
        pair<pii, pii >  x = { { l , r } , { h , c } };
        if(p == 0) a .push_back( x );
        else b .push_back( x);
    }
    a.push_back({{1e9,1e9}, {0,0}});
    b.push_back({{1e9,1e9}, {0,0}});
    int x = a.size(), y = b.size();
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    dp[0][0] = 0;
    for(int i = 0; i < x; i++)
        al[i] = a[i].F.F,
        ar[i] = a[i].F.S,
        ah[i] = a[i].S.F,
        ac[i] = a[i].S.S;
    for(int i = 0; i < y; i++)
        bl[i] = b[i].F.F,
        br[i] = b[i].F.S,
        bh[i] = b[i].S.F,
        bc[i] = b[i].S.S;
    for(int i = 0; i < x; i++)
        for(int j = 0; j < y; j++){
            ans = max(ans, dp[i][j]);
            if(ar[i] < br[j]){
                for(int k = i + 1; k < x; k++){
                    if(al[k] >= ar[i] &&
                       (ah[k] + bh[j] <= w ||
                       al[k] >= br[j] ||
                       ar[k] <= bl[j])){
                            dp[k][j] = max(dp[k][j], dp[i][j] + ac[k]);
                       }
                }
            }
            else{
                for(int k = j + 1; k < y; k++){
                    if(bl[k] >= br[j] &&
                       (bh[k] + ah[i] <= w ||
                       bl[k] >= ar[i] ||
                       br[k] <= al[i])){
                            dp[i][k] = max(dp[i][k], dp[i][j] + bc[k]);
                       }
                }
            }
        }
    cout << ans << endl;
}

Compilation message (stderr)

mat.cpp:10:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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