제출 #1304790

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304790		BilAktauAlmansur	Financial Report (JOI21_financial)	C++20	0 / 100	4094 ms	13596 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];
vector<int> g[N];
void solve() {
    cin>>n>>d;
    for(int i = 1; i <= n; i++) {
        cin>>a[i];
        dp[i] = 0;
    }
    // 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++) {
        g[a[i]].push_back(i);
    }
    for(int i = 1; i <= n; i++) {
        for(auto j : g[i]) {
            for(int k = j - 1; k >= max(1ll, j - d); k--) {
                if(a[j] == a[k])continue;
                dp[j] = max(dp[j], dp[k] + 1);
            }
            dp[j] = max(dp[j], 1ll);
        }
        // for(int j = 1; j <= n; j++) {
        //     cout << dp[j] << ' ';
        // }
        // cout << '\n';
    }
    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: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35