Submission #1243966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243966		sula2	Financial Report (JOI21_financial)	C++20	65 / 100	4094 ms	3776 KiB

Main

#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 (n == 1) {
        cout << 1;
        exit(0);
        // this shit so retarded wtf
    }
    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 {
        int dp[n];
        for (int i = n-1; i >= 0; i--) {
            dp[i] = 1;
            int last = i;
            for (int j = i+1; j < n; j++) {
                if (j - last > d) break;
                if (a[j] <= a[i]) last = j;
                else dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        cout << *max_element(dp, dp + n);
    }
}

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