Submission #600464

#	Time	Username	Problem	Language	Result	Execution time	Memory
600464		Plurm	Financial Report (JOI21_financial)	C++11	33 / 100	4051 ms	314904 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
int seg[8192][16384];
int lb[16384];
int rb[16384];

int a[300005];
int dp[7005][7005]; // dp[last][max]

void build(int c, int l, int r){
  lb[c] = l;
  rb[c] = r;
  if(l == r) return;
  int k = (l+r)/2;
  build(2*c, l, k);
  build(2*c+1, k+1, r);
}

void update(int t, int c, int i, int x){
  if(lb[c] == rb[c]){
    seg[t][c] = x;
    return;
  }
  int k = (lb[c] + rb[c]) / 2;
  if(i <= k) update(t, 2*c, i, x);
  else update(t, 2*c+1, i, x);
  seg[t][c] = max(seg[t][2*c], seg[t][2*c+1]);
}

int query(int t, int c, int l, int r){
  if(r < l) return -1000;
  if(lb[c] == l && rb[c] == r) return seg[t][c];
  int k = (lb[c] + rb[c])/2;
  if(l <= k && k < r) return max(query(t, 2*c, l, k), query(t, 2*c+1, k+1, r));
  else if(r <= k) return query(t, 2*c, l, r);
  else return query(t, 2*c+1, l, r);
}

int main(){
  int n, d;
  scanf("%d%d",&n,&d);
  for(int i = 1; i <= n; i++){
    scanf("%d", a+i);
  }
  if(n > 7000){
    vector<int> lis;
    for(int i = 1; i <= n; i++){
      auto it = lower_bound(lis.begin(), lis.end(), a[i]);
      if(it == lis.end()) lis.push_back(a[i]);
      else *it = a[i];
    }
    printf("%d\n", lis.size());
    return 0;
  }
  build(1, 1, n);
  for(int i = 1; i <= n; i++){
    for(int j = 1; j < i; j++){
      if(a[j] < a[i]) continue;
      // dp[i][j] <- dp[k][j]
      dp[i][j] = max(dp[i][j], query(j, 1, max(1, i-d), i-1));
      update(j, 1, i, dp[i][j]);
    }
    // dp[i][i]
    dp[i][i] = 1;
    for(int j = 0; j < i; j++){
      if(a[j] >= a[i]) continue;
      dp[i][i] = max(dp[i][i], query(j, 1, max(1, i-d), i-1) + 1); // find max dp[i-d..i-1][j]
    }
    update(i, 1, i, dp[i][i]);
  }
  int ans = 0;
  for(int j = 0; j <= n; j++) ans = max(ans, dp[n][j]);
  printf("%d\n", ans);
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:53:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   53 |     printf("%d\n", lis.size());
      |             ~^     ~~~~~~~~~~
      |              |             |
      |              int           std::vector<int>::size_type {aka long unsigned int}
      |             %ld
Main.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%d%d",&n,&d);
      |   ~~~~~^~~~~~~~~~~~~~
Main.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d", a+i);
      |     ~~~~~^~~~~~~~~~~

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