Submission #705005

#	Time	Username	Problem	Language	Result	Execution time	Memory
705005		Cyanmond	Financial Report (JOI21_financial)	C++17	14 / 100	4082 ms	5416 KiB

Main

#include <bits/stdc++.h>

constexpr int inf = 1 << 30;

class SegTree {
    int n, size;
    std::vector<int> data;
    void update(int i) {
        data[i] = std::max(data[2 * i], data[2 * i + 1]);
    }

    public:
    SegTree(int n_) : n(n_) {
        size = 1;
        while (size < n) size *= 2;
        data.assign(2 * size, -inf);
    }

    void set(int i, int v) {
        i += size;
        data[i] = v;
        while (i != 1) {
            i /= 2;
            update(i);
        }
    }

    int fold(int l, int r) {
        int res = -inf;
        for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = std::max(res, data[l++]);
            if (r & 1) res = std::max(res, data[--r]);
        }
        return res;
    }
};

int solve(int D, std::vector<int> A) {
    const int N = (int)A.size();
    {
        // press
        auto B = A;
        std::sort(B.begin(), B.end());
        B.erase(std::unique(B.begin(), B.end()), B.end());
        for (auto &e : A) e = (int)(std::lower_bound(B.begin(), B.end(), e) - B.begin()) + 1;
    }

    std::vector<int> keepLimit(N, N);
    for (int i = 0; i < N; ++i) {
        int last = i;
        for (int j = i + 1; j < N; ++j) {
            if (j - last > D) {
                keepLimit[i] = j;
                break;
            }
            if (A[j] <= A[i]) {
                last = j;
            }
        }
    }

    SegTree seg(N + 1);
    seg.set(0, 0);
    std::vector<std::vector<int>> eraseList(N + 1);
    for (int i = 0; i < N; ++i) {
        for (const int j : eraseList[i]) {
            seg.set(j, -inf);
        }
        const int f = seg.fold(0, A[i]);
        seg.set(A[i], f + 1);
        eraseList[keepLimit[i]].push_back(A[i]);
    }
    return seg.fold(0, N + 1);
}

int solveNaive(int D, std::vector<int> A) {
    const int N = (int)A.size();
    int answer = 1;
    for (int bits = 0; bits < (1 << N); ++bits) {
        int last = -1;
        if (not(bits & (1 << (N - 1)))) {
            continue;
        }
        int res = 0, ma = -1;
        for (int i = 0; i < N; ++i) {
            if (bits & (1 << i)) {
                if (last == -1) {
                    last = i;
                } else {
                    if (i - last > D) {
                        res = -1;
                        break;
                    }
                }
                last = i;
                if (A[i] > ma) {
                    ++res;
                    ma = A[i];
                }
            }
        }
        answer = std::max(answer, res);
    }
    return answer;
}

int main() {
    int N, D;
    std::cin >> N >> D;
    std::vector<int> A(N);
    for (auto &e : A) {
        std::cin >> e;
    }
    std::cout << solveNaive(D, A) << std::endl;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35