Submission #1304795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304795		BilAktauAlmansur	Financial Report (JOI21_financial)	C++20	48 / 100	4090 ms	7596 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const int N = 3e5 + 7, M = 5e6 + 7, mod = 1e9 + 7;

int n, d, a[N], dp[N], last[N];
vector<int> g[N];
void solve() {
    cin>>n>>d;
    for(int i = 1; i <= n; i++) {
        cin>>a[i];
    }
    // if(d == 1) {
    //     int mx = 0;
    //     stack<int> st;
    //     for(int i = n; i >= 1; i--) {
    //         while(st.size() && a[st.top()] <= a[i])st.pop();
    //         if(!st.size())dp[i] = 1;
    //         else dp[i] = dp[st.top()] + 1;
    //         st.push(i);
    //         mx = max(mx, dp[i]);
    //     }
    //     cout << mx << '\n';
    //     return;
    // }
    vector<int> vec;
    for(int i = 1; i <= n; i++) {
        vec.push_back(a[i]);
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    map<int, int> mp;
    int cur = 0;
    for(auto i : vec)mp[i] = ++cur;
    for(int i = 1; i <= n; i++)a[i] = mp[a[i]];
    for(int i = 1; i <= n; i++) {
        int cnt = 1;
        for(int j = 1; j <= n; j++) {
            if(a[i] > j) {
                if(i - last[j] <= d)cnt = max(cnt, dp[j] + 1);
            }else {
                if(i - last[j] <= d)last[j] = i;
            }
        }
        if(dp[a[i]] <= cnt) {
            dp[a[i]] = cnt;
            last[a[i]] = i;
        }
    }
    int mx = 0;
    for(int i = 1; i <= n; i++)mx = max(mx, dp[i]);
    cout << mx << '\n';
}
signed main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    int T = 1;
    // cin>>T;
    while(T --)solve();
}

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