Submission #534277

#	Time	Username	Problem	Language	Result	Execution time	Memory
534277		Monarchuwu	Financial Report (JOI21_financial)	C++17	40 / 100	114 ms	9000 KiB

Main

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;

const int N = 3e5 + 7, N2 = 400 + 2;
int n, d;
int a[N];

int b[N];
void compress() {
    copy(a + 1, a + n + 1, b + 1);
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
}

// dp[i][j] -> dp[k][max(j, a[k])]
// j <  a[k] : dp[k][a[k]] <- dp[i][j] + 1
//          => dp[k][a[k]] <- max(dp[i][a[k] - 1], ..., dp[i][0]) + 1
// j >= a[k] : dp[k][  j ] <- dp[i][j]
//
// dp[i][j] -> dp[k][a[j] > a[k] ? j : k]
void maximize(int &a, int b) { if (a < b) a = b; }
int dp[N2][N2];
void subtask2() {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= i; ++j)
            for (int k = i + 1; k <= min(n, i + d); ++k) {
                if (a[j] < a[k])
                    maximize(dp[k][k], dp[i][j] + 1);
                else maximize(dp[k][j], dp[i][j]);
            }

    int ans(0);
    for (int i = 1; i <= n; ++i)
        maximize(ans, dp[n][i]);
    cout << ans << '\n';
}

int L[N], cnt[N];
int st[N], top;
void subtask4() {
    for (int i = 1; i <= n; ++i) {
        while (top && a[st[top]] < a[i]) --top;
        ++cnt[L[i] = st[top]];
        st[++top] = i;
    }

    int ans(0), sum(1);
    for (int i = 0; i < n; ++i) {
        sum += cnt[i] - 1;
        ans = max(ans, sum);
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> d;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    compress();

    if (n <= 400) subtask2();
    else if (d == 1) subtask4();
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

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