Submission #1078007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078007		abdelhakim	Financial Report (JOI21_financial)	C++14	0 / 100	4091 ms	10712 KiB

Main

#include <bits/stdc++.h>
#define mod 1000000007LL
#define inf 1e17
#define ll long long
using namespace std;

void printvec(vector<ll> vec) {
    for (auto &&e : vec) {
        cout << e << ' ';
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, d;
    cin >> n>> d;
    if(d==1)
    {
        vector<pair<ll,ll>> a(n);
        for(int i=0; i < n; i++)
        {
            ll x;
            cin >> x;
            a[i] = {x, i};
        }
        sort(a.begin(), a.end(), greater<pair<ll,ll>>());
        set<ll> indices;
        map<ll,ll> nxtmx;
        for (int i = 0; i < n; i++)
        {
            auto it = lower_bound(indices.begin(), indices.end(), a[i].second);
            if(it == indices.end()) nxtmx[i] = -1;
            else nxtmx[i] = *it;
            indices.insert(a[i].second);
        }
        vector<ll> dp(n,1);
        dp.back() = 1;
        for (int i = n-2; i >= 0; i--)
        {
            if(nxtmx[i]!=-1) dp[i]+=dp[nxtmx[i]];
        }
        cout << *max_element(dp.begin(), dp.end()) << endl;
    }
    else{
    vector<ll> a(n);
    for(int i=0; i < n; i++) cin >> a[i];
    vector<ll> dp(n,1);
    dp.back() = 1;
    for (int i  = n-2; i >= 0; i--)
    {
        ll cur = 0;
        for (int j=i+1; j < n; j++)
        {
            if(a[j] > a[i])
            {
                cur++;
                dp[i] = max(dp[i], 1 + dp[j]);
                if(cur == d)break;
            }
            else cur = 0;
        }
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
    }
}

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