oj.uz

Submission #71270

# Submission time Handle Problem Language Result Execution time Memory
71270 2018-08-24T09:33:26 Z 3zp 매트 (KOI15_mat) C++14
57 / 100
 1000 ms 12784 KB 
#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++){
                for(int p = i - 1; p >= 0; p--){
                    if(al[i] >= ar[p] &&
                       (ah[i] + bh[j] <= w ||
                       al[i] >= br[j] ||
                       ar[i] <= bl[j]) &&
                       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] &&
                    (bh[j] + ah[i] <= w ||
                    bl[j] >= ar[i] ||
                    br[j] <= al[i]) &&
                    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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 3 ms 592 KB Output is correct
5 Correct 2 ms 644 KB Output is correct

Subtask #2
13.0 / 13.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1004 KB Output is correct
2 Correct 8 ms 1004 KB Output is correct
3 Correct 7 ms 1132 KB Output is correct
4 Correct 6 ms 1132 KB Output is correct
5 Correct 7 ms 1132 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 12780 KB Output is correct
2 Correct 52 ms 12780 KB Output is correct
3 Correct 43 ms 12784 KB Output is correct
4 Correct 44 ms 12784 KB Output is correct
5 Correct 36 ms 12784 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 12784 KB Time limit exceeded
2 Halted 0 ms 0 KB -