Submission #1221859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221859		spetr	Financial Report (JOI21_financial)	C++20	0 / 100	1061 ms	1114112 KiB

Main

#include <bits/stdc++.h>
#include <algorithm>

using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>


int LIS(vl& nums) {
    vl dp;
    for (int x : nums) {
        auto it = std::lower_bound(dp.begin(), dp.end(), x);
        if (it == dp.end())
            dp.push_back(x);
        else
            *it = x;
    }
    return dp.size();
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, d;
    cin >> n >> d;

    vl nums;
    for (ll i = 0; i < n; i++){
        ll num;
        cin >> num;
        nums.push_back(num);
    }

    if (d == 1){
        ll maximum = 0;
        ll c = 0;

        for (ll i = 0; i < n; i++){
            if (nums[i] > maximum){
                maximum = nums[i];
                c ++;
            }

        }
        cout << c << "\n";
    }
    /*/else if (d == n){
        cout << LIS(nums) << "\n";
    }/*/
    else{
        vll dp;
        for (ll i = 0; i < n; i++){
            vl radek;
            for (ll j = 0; j < n; j++){
                radek.push_back(1e7);
            }
            dp.push_back(radek);
        }

        for (ll i = 0; i < n; i++){
            ll num = nums[i];
            ll nula = 0;
            dp[0][i] = num;
            for (ll j = n-1; j > 0; j--){
                for (ll t = i-1; t >= max(nula, i-d); t--){
                    dp[j][i] = min(dp[j][i], dp[j][t]);
                }
            
                dp[j][i] = max(dp[j][i], num);
            }
            for (ll j = n-1; j > 0; j--){
                for (ll t = i-1; t >= max(nula, i-d); t--){
                    if (dp[j][i] > dp[j-1][t] && dp[j-1][t] < num){
                        dp[j][i] = num;
                    }
                }
            }
        }
        ll skore = 1;
        for (ll i = 0; i < n; i++){
            if (dp[i][n-1]!= 1e7){
                skore = i+1;
            }
        }

        cout << skore;


    }


    
    return 0;
}

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