oj.uz

Submission #85739

# Submission time Handle Problem Language Result Execution time Memory
85739 2018-11-21T12:21:55 Z chunghan 매트 (KOI15_mat) C++17
100 / 100
 276 ms 72816 KB 
#include<bits/stdc++.h>

using namespace std;

int N, W, rst;

class Line {
    public:
        int x, i;
        bool r;
        Line(int i, int x, bool r): i(i), x(x), r(r) {}
        bool operator < (const Line &l) const {
            return x < l.x;
        }
};

class Mat {
    public:
        int P, L, R, H, K;
        Mat(int P, int L, int R, int H, int K): P(P), L(L), R(R), H(H), K(K) {}
        bool meet(const Mat &M) const {
            if (R <= M.L || L >= M.R) return false;
            if (P == M.P) return true;
            return H + M.H > W;
        }
        bool operator < (const Mat &M) const {
            return R != M.R ? R < M.R : L < M.L;
        }
};

vector<Mat> A;
vector<Line> B;
int D[3005][6005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> N >> W;
    for (int i = 0; i < N; i++) {
        int P, L, R, H, K;
        cin >> P >> L >> R >> H >> K;
        A.push_back(Mat(P, L, R, H, K));
    }
    sort(A.begin(), A.end());
    for (int i = 0; i < N; i++) {
        B.push_back(Line(i, A[i].L, false));
        B.push_back(Line(i, A[i].R, true));
    }
    sort(B.begin(), B.end());
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 2*N; j++) {
            if (B[j].x > A[i].R) break;
            D[i][j] = A[i].K;
            if (j > 0) D[i][j] = max(D[i][j], D[i][j-1]);
            if (B[j].r) {
                int k = B[j].i;
                if (A[k].R <= A[i].L) {
                    D[i][j] = max(D[i][j], D[k][j] + A[i].K);
                } else if (!A[i].meet(A[k])) {
                    if (A[k].L < A[i].L) {
                        int h = upper_bound(B.begin(), B.end(), Line(-1, A[i].L, 0)) - B.begin();
                        D[i][j] = max(D[i][j], D[k][h-1] + A[i].K);
                    } else {
                        int h = upper_bound(B.begin(), B.end(), Line(-1, A[k].L, 0)) - B.begin();
                        D[i][j] = max(D[i][j], D[i][h-1] + A[k].K);
                    }
                }
            }
            rst = max(D[i][j], rst);
        }
    }
    cout << rst;
    return 0;
}

Compilation message

mat.cpp: In constructor 'Line::Line(int, int, bool)':
mat.cpp:9:16: warning: 'Line::i' will be initialized after [-Wreorder]
         int x, i;
                ^
mat.cpp:9:13: warning:   'int Line::x' [-Wreorder]
         int x, i;
             ^
mat.cpp:11:9: warning:   when initialized here [-Wreorder]
         Line(int i, int x, bool r): i(i), x(x), r(r) {}
         ^~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 568 KB Output is correct
2 Correct 2 ms 612 KB Output is correct
3 Correct 2 ms 740 KB Output is correct
4 Correct 2 ms 888 KB Output is correct
5 Correct 2 ms 888 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1820 KB Output is correct
2 Correct 4 ms 1820 KB Output is correct
3 Correct 4 ms 1828 KB Output is correct
4 Correct 3 ms 1836 KB Output is correct
5 Correct 4 ms 1844 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 58092 KB Output is correct
2 Correct 116 ms 58168 KB Output is correct
3 Correct 129 ms 58556 KB Output is correct
4 Correct 126 ms 58716 KB Output is correct
5 Correct 102 ms 62820 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 64316 KB Output is correct
2 Correct 248 ms 64316 KB Output is correct
3 Correct 276 ms 64316 KB Output is correct
4 Correct 247 ms 64316 KB Output is correct
5 Correct 228 ms 64316 KB Output is correct
6 Correct 121 ms 64316 KB Output is correct
7 Correct 224 ms 64316 KB Output is correct
8 Correct 220 ms 64316 KB Output is correct
9 Correct 253 ms 72816 KB Output is correct
10 Correct 215 ms 72816 KB Output is correct