Submission #600434

#	Time	Username	Problem	Language	Result	Execution time	Memory
600434		Plurm	Financial Report (JOI21_financial)	C++11	33 / 100	4061 ms	121932 KiB

Main

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

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

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;
  }
  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--){
        if(a[j] < a[k]) continue;
        dp[i][j] = max(dp[i][j], dp[k][j]);
      }
    }
    // dp[i][i]
    dp[i][i] = 1;
    for(int k = i-1; k >= i-d && k > 0; k--){
      for(int j = 0; j <= k; j++){
        if(a[j] >= a[i]) continue;
        dp[i][i] = max(dp[i][i], dp[k][j] + 1);
      }
    }
  }
  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:20:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   20 |     printf("%d\n", lis.size());
      |             ~^     ~~~~~~~~~~
      |              |             |
      |              int           std::vector<int>::size_type {aka long unsigned int}
      |             %ld
Main.cpp:9:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |   scanf("%d%d",&n,&d);
      |   ~~~~~^~~~~~~~~~~~~~
Main.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     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