Submission #1267358

#TimeUsernameProblemLanguageResultExecution timeMemory
1267358vpinxRabbit Carrot (LMIO19_triusis)C++20
0 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int INF = 1e9 + 5; int solve() { int n, m; cin >> n >> m; vector<int> v; for (int i = 0; i < n; i++) { int a; cin >> a; if (a <= m * (i + 1)) v.push_back(m * (i + 1) - a); } vector<int> dp(v.size() + 1, INF); dp[0] = 0; for (int i = 0; i < v.size(); i++) { int idx = lower_bound(dp.begin(), dp.end(), v[i]) - dp.begin(); if (v[i] < dp[idx]) dp[idx] = v[i]; } int ans = 0; for (int i = 1; i <= v.size(); i++) { if (dp[i] < INF) ans = i; } return n - ans; } int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...