Submission #71271

#	Time	Username	Problem	Language	Result	Execution time	Memory
71271		3zp	매트 (KOI15_mat)	C++14	57 / 100	1085 ms	12964 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++){
                if(!((bh[j] + ah[i] <= w ||
                    bl[j] >= ar[i] ||
                    br[j] <= al[i]))) continue;
                for(int p = i - 1; p >= 0; p--){
                    if(al[i] >= ar[p] &&
                       ar[p] < br[j]){
                            dp[i][j] = max(dp[i][j], dp[p][j] + ac[i]);
                       }
                }
            for(int p = j - 1; p >= 0; p--){
                if(bl[j] >= br[p] &&
                    ar[i] >= br[p]){
                        dp[i][j] = max(dp[i][j], dp[i][p] + bc[j]);
                    }
                }
            ans = max(ans, dp[i][j]);
        }
    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