Submission #1243882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243882		sula2	Jail (JOI22_jail)	C++20	0 / 100	0 ms	324 KiB

jail

#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
#define Z string::npos
using namespace std;
using namespace chrono;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,d; cin >> n >> d;
    int a[n];
    for (int& x : a) cin >> x;

    if (d == 1) {
        vector<int> st;
        int ans = 0;
        for (int i = n-1; i >= 0; i--) {
            while (!st.empty() && a[i] >= a[st.back()])
                st.pop_back();
            st.push_back(i);
            ans = max(ans, (int)st.size());
        }
        cout << ans;
    } else if (d == n) {
        vector<int> lis;
        for (int i = 0; i < n; i++) {
            auto it = lower_bound(all(lis), a[i]);
            if (it == lis.end()) {
                lis.push_back(a[i]);
            } else {
                *it = a[i];
            }
        }
        cout << lis.size();
    } else if (n <= 20) {
        int ans = 0;
        for (int mask = 1 << n-1; mask < 1 << n; mask++) {
            int mx = -1, cnt = 0;
            vector<int> pos;
            for (int i = 0; i < n; i++) {
                if ((mask >> i) & 1) {
                    pos.push_back(i);
                    cnt += a[i] > mx;
                    mx = max(mx, a[i]);
                }
            }
            for (int i = 0; i+1 < pos.size(); i++) {
                if (pos[i+1] - pos[i] > d) {
                    ans = 0;
                }
            }
            ans = max(ans, cnt);
        }
        cout << ans;
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23