Submission #1243896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243896		urosk	Financial Report (JOI21_financial)	C++17	48 / 100	4093 ms	9900 KiB

Main

#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pld = pair<ld,ld>;

const ll maxn = 300005;
ll n,d;
ll a[maxn];
pll dp[maxn];
vector<ll> v;
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> d;
    for(ll i = 1;i<=n;i++) cin >> a[i],v.pb(a[i]);
    sort(all(v));
    for(ll i = 1;i<=n;i++) a[i] = lower_bound(all(v),a[i])-v.begin()+1;
    for(ll i = 0;i<=n;i++) dp[i] = {0,0};
    for(ll i = 1;i<=n;i++){
        ll x = a[i];
        for(ll j = 0;j<=n;j++) if(dp[j].sc<i-d) dp[j] = {-1,-1};
        // for(ll j = 0;j<=n;j++) cerr<<"{ "<<dp[j].fi<<", "<<dp[j].sc<<"} ";
        // cerr<<endl;
        for(ll j = x;j<=n;j++){
            if(dp[j].fi!=-1){
                dp[j].sc = i;
            }
        }
        for(ll j = 0;j<x;j++){
            if(dp[j].fi!=-1){
                dp[x] = max(dp[x],{dp[j].fi+1,i});
            }
        }
        dp[x] = max(dp[x],{1,i});
    }
    for(ll j = 0;j<=n;j++) if(dp[j].sc<n-d) dp[j] = {-1,-1};
    pll ans = {-1,-1};
    for(ll i = 0;i<=n;i++) ans = max(ans,dp[i]);
    cout<<ans.fi<<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