Submission #600455

#	Time	Username	Problem	Language	Result	Execution time	Memory
600455		Plurm	Financial Report (JOI21_financial)	C++11	5 / 100	46 ms	3648 KiB

Main

#include <bits/stdc++.h>
using namespace std;

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

class comp{
  public:
  bool operator()(int x, int y){
    return a[x] < a[y];
  }
};

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;
  }
  map<int,int,comp> mp;
  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]
      for(int k = i-1; k >= i-d && k > 0; k--){
        dp[i][j] = max(dp[i][j], dp[k][j]);
      }
    }
    // dp[i][i]
    dp[i][i] = 1;
    auto it = mp.lower_bound(i);
    if(it != mp.begin()){
      --it;
      bool ok = true;
      while(it->second < i-d){
        it = mp.erase(it);
        if(it == mp.begin()){
          ok = false;
          break;
        }
        --it;
      }
      if(ok) dp[i][i] = dp[it->second][it->first] + 1;
    }
    for(int j = 0; j <= i; j++){
      it = mp.lower_bound(j);
      while(it != mp.end() && dp[it->second][it->first] <= dp[i][j]){
        it = mp.erase(it);
      }
      if(it == mp.begin()){
        mp[j] = i;
      }else{
        --it;
        if(dp[it->second][it->first] < dp[i][j]) mp[j] = 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:27:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   27 |     printf("%d\n", lis.size());
      |             ~^     ~~~~~~~~~~
      |              |             |
      |              int           std::vector<int>::size_type {aka long unsigned int}
      |             %ld
Main.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   scanf("%d%d",&n,&d);
      |   ~~~~~^~~~~~~~~~~~~~
Main.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%d", a+i);
      |     ~~~~~^~~~~~~~~~~

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