| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1099310 | 2024-10-11T07:08:23 Z | hegoplay | Rabbit Carrot (LMIO19_triusis) | C++17 | 0 ms | 0 KB |
/*
-
+=
@@@@@%
+@@@@@@+
%@@@@@#%
@@@@@@@@=:
+****************** =@@@@@@@@@%
=***********#*******+
%@@@@@@@@@@@@@@@@@@@@= @@@@@@@@@@%
#@@@@@@@@@@@@@@@@@@@@@@
+@@@@@@@@@@@@@@@@@@@@@+ +@@#@@@@@@@@%
@@@@@@@@@@@@@@@@@@@@@@@=
+@@@@% *@@%@@@@@@@@@= %@@@%
@@@@@# *@@@@@@@@@@@@# #@@@@@
%@@@@% +@@@@@@@@@@@@%
@@@@@@@@@@@@@@@@@@@@%
#@@@@@ =#+@@@@@@@@#@%
=@@@@@@@@@@@@@@@@@@@@*
+@@@@@+ #@@@@@@% =@@@@@=
=@@@@@* #@@@@@@# @@@@@*
#@@@@@@@@@@@@@@@@@@@@@ +@@@@@@# *@@@@@@@@@@@@@@@@@@@@@@#
+@@@@@@@@@@@@@@@@@@@@= %@@@@@% +@@@@@@@@@@@@@@@@@@@@@@+
+*#************##* =@@@@@#+ ###**##**#*******##*+
=@@@@@@%
+** =+=
Michael Jackson peeks
*/
#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// Including tree_order_statistics_node_update
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define inf 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(), (x).end()
#define yes cout << "YES\n";
#define no cout << "NO\n";
#define sz(x) (int)(x).size()
#define el "\n"
typedef long long ll;
typedef long double ld;
#define int long long
using namespace std;
using namespace __gnu_pbds;
#define indexed_set \
tree<int, null_type, less<int>, rb_tree_tag, \
tree_order_statistics_node_update>
void setIO(string name = "") {
if (sz(name)) {
freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
freopen((name + ".out").c_str(), "w", stdout);
}
}
void solve() {
int n;
cin >> n;
int m;
cin >> m;
vector<int> vt(n + 1);
for (int i = 1; i <= n; i++) {
cin >> vt[i];
}
vt[0] = 0;
set<int> s;
map<int, pair<int, int>> mp;
// tim
// vi tri va so luong su thay doi can
s.insert(0);
mp[0] = {0, 0};
for (int i = 1; i < vt.size(); i++) {
int &x = vt[i];
int val = x - m * i;
if(val > 0){
continue;
}
auto it = s.lower_bound(val);
auto cur = mp[*it];
if (mp.contains(val) && mp[val].second < i - cur.first - 1 + cur.second){
continue;
}
else mp[val] = {i, i - cur.first - 1 + cur.second};
s.insert(val);
}
ll res = LLONG_MAX;
for (auto x : mp) {
res = min(res, n - x.second.first + x.second.second);
}
cout << res;
}
signed main() {
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// #endif
// setIO("cowjog");
ios ::sync_with_stdio(false);
cin.tie(nullptr);
ll t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}