oj.uz

Submission #71269

# Submission time Handle Problem Language Result Execution time Memory
71269 2018-08-24T09:27:05 Z 3zp 매트 (KOI15_mat) C++14
57 / 100
 1000 ms 12924 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++){
            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

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 340 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 3 ms 416 KB Output is correct
5 Correct 3 ms 596 KB Output is correct

Subtask #2
13.0 / 13.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12796 KB Output is correct
2 Correct 35 ms 12800 KB Output is correct
3 Correct 35 ms 12844 KB Output is correct
4 Correct 36 ms 12924 KB Output is correct
5 Correct 28 ms 12924 KB Output is correct

Subtask #5
0 / 43.0

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