Submission #1231666

#TimeUsernameProblemLanguageResultExecution timeMemory
1231666nanh0607Rabbit Carrot (LMIO19_triusis)C++20
63 / 100
20 ms1096 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, l, r) for (int i=l; i<=r; i++) void solve() { int n, m; cin >> n >> m; vector<int> dp(n+1, 1e9); dp[0] = 0; // aj <= ai + M*(j-i) // M*j - aj >= M*i - ai // bj >= bi int res = 0; FOR(i, 1, n) { int a; cin >> a; int b = m*i-a; if (b < 0) continue; auto it = upper_bound(dp.begin(), dp.end(), b); int idx = it - dp.begin(); dp[idx] = min(dp[idx], b); res = max(res, idx); } cout << n-res; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...