Submission #428397

#	Time	Username	Problem	Language	Result	Execution time	Memory
428397		muhammad_hokimiyon	Financial Report (JOI21_financial)	C++14	0 / 100	4058 ms	6840 KiB

Main

#include <bits/stdc++.h>

#define fi first
#define se second
#define ll long long
#define dl double

using namespace std;

const int N = 1e6 + 7;
const long long mod = 1e9 + 7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());



void solve()
{
        int n,D;
        cin >> n >> D;
        vector<int> a(n + 1, 0);
        vector<int> id;
        for(int i = 1; i <= n; i++){
                cin >> a[i];
                id.push_back(i);
        }
        sort(id.begin(), id.end(), [&](int i, int j){
                return a[i] < a[j];
        });
        vector<int> d(n + 1, 0);
        for(int i = 0; i < n; i++){
                int j = i;
                vector<int> g;
                while(j < n && a[id[i]] == a[id[j]]){
                        int x = id[j];
                        int mx = 1;
                        for(int h = x; h >= max(1, x - D); h--){
                                mx = max(mx, d[h] + 1);
                        }
                        g.push_back(mx);
                        j++;
                }
                for(int h = i; h < j; h++){
                        d[id[h]] = g[h - i];
                }
                i = j - 1;
        }
        cout << *max_element(d.begin(), d.end());
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    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