Submission #1244165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244165		emad234	Financial Report (JOI21_financial)	C++20	65 / 100	4094 ms	6836 KiB

Main

#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<int,int>
const int mxN = 3e5 + 5;
const int mod = 1e9 + 7;
using namespace std;
int dp[mxN];
int a[mxN];
int n,d;
int t[mxN];
signed main(){
  cin >>n>>d;
  for(int i = 1;i <= n;i++) cin >>a[i];
  if(d == n){
    vector<int>v;
    for(int i = 1;i <= n;i++){
      if(v.empty() || lower_bound(v.begin(),v.end(),a[i]) == v.end()) {
        v.push_back(a[i]);
        // cout<<v.size()<<' ';
        continue;
      }
      int x = lower_bound(v.begin(),v.end(),a[i]) - v.begin();
      v[x] = a[i];
      // cout<<v.size()<<' ';
    }
    cout<<v.size();
    return 0;
  }
  if(d == 1){
    int ans = 0;
    priority_queue<pii,vector<pii>,greater<pii>>q;
    for(int i = 1;i <= n;i++){
      dp[i] = 1;
      while(q.size() && q.top().F < a[i]){
        dp[i] = max(dp[i],dp[q.top().S] + 1);
        q.pop();
      }
      q.push({a[i],i});
      ans = max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
  }
  int ans = 0;
  for(int i = 1;i <= n;i++){
    dp[i] = 1;
    t[i] = i;
    for(int j = 1;j < i;j++){
      if(i - t[j] <= d){
        if(a[j] >= a[i]) t[j] = i;
        else{
          dp[i] = max(dp[i],dp[j] + 1);
        }
      }
    }
    ans = max(ans,dp[i]);
  }
  cout<<ans;
}

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