Submission #424385

#	Time	Username	Problem	Language	Result	Execution time	Memory
424385		Osama_Alkhodairy	Financial Report (JOI21_financial)	C++17	48 / 100	4083 ms	6076 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

int n, d;
vector <int> a;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> d;
    a.resize(n);
    for(auto &i : a) cin >> i;
    vector <pair <int, int> > all;
    for(int i = 0 ; i < n ; i++){
        all.push_back(make_pair(a[i], i));
    }
    sort(all.begin(), all.end(), [&](pair <int, int> &l, pair <int, int> &r){
        return make_pair(l.first, -l.second) < make_pair(r.first, -r.second);
    });
    set <pair <int, int> > s;
    vector <int> f(n);
    for(auto &i : all){
        int idx = i.second;
        auto cur = make_pair(idx, idx);
        auto it = s.lower_bound(make_pair(idx, -1));
        vector <pair <int, int> > to_erase;
        if(it != s.end() && idx + d >= it->first){
            cur.second = it->second;
            to_erase.push_back(*it);
        }
        if(it != s.begin()){
            it--;
            if(idx - d <= it->second){
                cur.first = it->first;
                cur.second = max(cur.second, it->second);
                to_erase.push_back(*it);
            }
        }
        for(auto &j : to_erase){
            s.erase(j);
        }
        f[idx] = min(cur.second + d, n - 1);
        s.insert(cur);
    }
    vector <int> dp(n);
    sort(all.begin(), all.end(), [&](pair <int, int> &l, pair <int, int> &r){
        return make_pair(-l.first, l.second) < make_pair(-r.first, r.second);
    });
    for(auto &i : all){
        int idx = i.second;
        dp[idx] = 1;
        for(int j = idx + 1 ; j <= f[idx] ; j++){
            dp[idx] = max(dp[idx], dp[j] + 1);
        }
    }
    int ans = 0;
    for(auto &i : dp) ans = max(ans, i);
    cout << ans << endl;
}

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