Submission #581601

#	Time	Username	Problem	Language	Result	Execution time	Memory
581601		colossal_pepe	Financial Report (JOI21_financial)	C++17	65 / 100	80 ms	4288 KiB

Main

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int n, d, a[300005], dp[7005];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> d;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    if (n <= 7000) {
        int ans = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            int x = i;
            for (int j = i - 1; j >= max(0, x - d); j--) {
                if (a[j] >= a[i]) continue;
                x = j;
                dp[i] = max(dp[i], 1 + dp[j]);
            }
            ans = max(ans, dp[i]);
        }
        cout << ans << '\n';
    } else if (d == 1) {
        int ans = 0;
        stack<int> s;
        for (int i = n - 1; i >= 0; i--) {
            while (not s.empty() and s.top() <= a[i]) s.pop();
            s.push(a[i]);
            ans = max(ans, (int)s.size());
        }
        cout << ans << '\n';
    } else if (d == n) {
        vector<int> lis;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            auto itr = lower_bound(lis.begin(), lis.end(), a[i]);
            if (itr == lis.end()) lis.push_back(a[i]);
            else lis[itr - lis.begin()] = a[i];
        }
        cout << lis.size() << '\n';
    } else {
        cout << "janina" << '\n';
    }
    return 0;
}

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