제출 #1243893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243893		sula2	Financial Report (JOI21_financial)	C++20	17 / 100	31 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 (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 <= 7000) {
        map<int, vector<int>> pos;
        for (int i = 0; i < n; i++) {
            pos[a[i]].push_back(i);
        }
        int v = 1;
        for (auto [x, list] : pos) {
            for (int i : list) {
                a[i] = v;
            }
            v++;
        }
        int dp[n][n+1] = {};
        for (int i = 0; i < n; i++) {
            for (int j = i-1; j >= 0 && j >= i-d; j--) {
                for (int m = 0; m <= n; m++) {
                    dp[i][m] = max(dp[i][m], dp[j][m]);
                    dp[i][max(a[i], m)] = max(dp[i][max(a[i], m)], dp[j][m] + (a[i] > m));
                }
            }
//            for (int j = 0; j <= n; j++) cout << dp[i][j] << " ";
//            cout << "\n";
        }
        cout << *max_element(dp[n-1], dp[n-1] + n+1);
    }
}

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