Submission #864247

#	Time	Username	Problem	Language	Result	Execution time	Memory
864247		vjudge1	Financial Report (JOI21_financial)	C++17	17 / 100	39 ms	8908 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 Glup(){

}

void Smart(){

}

void solve(){
  cin >> n >> D;
  a.resize(n);
  for (int i = 0; i < n; i++){
    cin >> a[i];
  }

  if (D == 1)D1();
  else if (D == n)DN();
  else if (n <= 7000)Glup();
  else Smart();
}

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

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