Submission #1128135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128135		micro7	Rabbit Carrot (LMIO19_triusis)	C++17	63 / 100	1093 ms	2196 KiB

triusis

#include <algorithm>
#include <cstdio>
#include <functional>
#include <map>
using namespace std;

constexpr int MAXN = 2e5;
int n, m, a[MAXN + 1];

int dp[MAXN + 1];
map<int, int, greater<>> s;

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }

  s[0] = 0;
  for (int i = 1; i <= n; ++i) {
    dp[i] = -1;
    for (auto [val, j] : s) {
      if (a[i] - i * m > val) {
        break;
      }
      if (dp[j] != -1) {
        dp[i] = max(dp[i], dp[j] + 1);
      }
    }
    s[a[i] - i * m] = i;
  }
  printf("%d", n - *max_element(dp, dp + n + 1));

  return 0;
}

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
triusis.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 0 / 37