Submission #1244137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244137		emad234	Financial Report (JOI21_financial)	C++20	0 / 100	4094 ms	2396 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;
  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;
  }
  for(int i = 1;i <= n;i++) cin >>a[i];
  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: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35