Submission #864271

#	Time	Username	Problem	Language	Result	Execution time	Memory
864271		vjudge1	Financial Report (JOI21_financial)	C++17	14 / 100	4026 ms	5348 KiB

Main

/* DK ORZ! */
#include "iostream"
#include "cstdio"
#include "cstdlib"
#include "algorithm"
#include "cmath"
#include "vector"
#include "set"
#include "map"
#include "unordered_set"
#include "unordered_map"
#include "queue"
#include "ctime"
#include "random"
#include "cassert"
#include "complex"
#include "string"
#include "cstring"
#include "chrono"
#include "bitset"
#include "array"
#include "stack"

#define endl '\n'
#define all(x) x.begin(), x.end()
#define int long long

using namespace std;

const int mod = 998244353;
const int nax = 300000;

int n, D;
vector <int> a;

void D1(){
  deque<int>s;
  int ans = 1;
  s.push_back(a.back());
  for (int i = n - 2; i >= 0; i--){
    while(s.size() > 0 && a[i] >= s.front())s.pop_front();
    s.push_front(a[i]);
    ans = max(ans, (int)s.size());
  }
  cout << ans << endl;
}

void DN(){
  vector <int> LIS;
  LIS.push_back(a[0]);
  for (int i = 1; i < n; i++){
    if (a[i] > LIS.back()){
      LIS.push_back(a[i]);
    }else{
      int ind = lower_bound(all(LIS), a[i]) - LIS.begin();
      LIS[ind] = a[i];
    }
  }
  cout << (int)LIS.size() << endl;
}

void Preglup(){
  int ans = 1;
  for (int i = 1; i < (1 << n); i++){
    vector <int> b;
    for (int j = 0; j < n; j++){
      if ((i & (1 << j))){
        b.push_back(j);
      }
    }
    if (b.back() != n - 1)continue;
    int ok = 1, mx = a[b[0]], cur = 1;
    for (int j = 1; j < (int)b.size(); j++){
      ok&= (b[j] - b[j - 1] <= D);
      if (a[b[j]] > mx)++cur;
      mx = max(mx, a[b[j]]);
    }
    if (ok)ans = max(ans, cur);
    
  }
  cout << ans << endl;
}

void NeTakaGlup(){
  int dp[n];
  for (int i = 0; i < n; i++){
    dp[i] = 1;
    int last = i;
    for (int j = i - 1; j >= 0; j--){
      if (last - j > D){
        break;
      }
      dp[i] = max(dp[i], 1 + dp[j]);
      if (a[j] < a[i]){
        last = j;
      }
    }
  }
  cout << dp[n - 1] << endl;
}

void Smart(){

}

void solve(){
  cin >> n >> D;
  a.resize(n);
  for (int i = 0; i < n; i++){
    cin >> a[i];
  }
  Preglup();
  return;
  if (D == 1)D1();
  else if (D == n)DN();
  else if (n <= 20)Preglup();
  else if (n <= 7000)NeTakaGlup();
  else Smart();
}

signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--){
    solve();
  }
  return 0;
}

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