#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define is insert
#define ll long long
#define V vector
#define MS multiset
#define PL pair<ll, ll>
#define F first
#define S second
#define PQ priority_queue
#define f0r(i, begin, end) for (ll i = begin; i < end; i ++)
#define For(i, end, begin) for (ll i = end; i > begin; i --)
#define all(x) x.begin(), x.end()
#define INF 1000000000000000000
#define inf 1000000000
#define MOD 998244353
#define len(x) (ll)x.size()
#define fileread(file) ifstream fin; fin.open((string)file + ".in"); ofstream fout; fout.open((string)file + ".out")
#define fastio ios_base::sync_with_stdio(0LL); cin.tie(nullptr)
template<typename T> istream& operator>>(istream& in, V<T>& a) {for(auto &x : a) in >> x; return in;};
template<typename T> ostream& operator<<(ostream& out, V<T>& a) {for(auto &x : a) out << x << ' '; return out;};
ll N, M;
V<ll> heights;
int main () {
cin >> N >> M;
heights.pb(0);
f0r (i, 1, N + 1) {
ll a; cin >> a;
heights.pb(-a + i * M);
}
V<ll> dp;
for (auto num : heights) {
ll pos = upper_bound(all(dp), num) - dp.begin();
if (num < 0) continue;
else if (dp.empty()) dp.pb(num);
else if (pos == len(dp)) dp.pb(num);
else {
dp[pos] = num;
}
}
cout << N - len(dp) + 1 << endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
300 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
300 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
296 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
2 ms |
380 KB |
Output is correct |
| 24 |
Correct |
1 ms |
436 KB |
Output is correct |
| 25 |
Correct |
1 ms |
436 KB |
Output is correct |
| 26 |
Correct |
2 ms |
468 KB |
Output is correct |
| 27 |
Correct |
1 ms |
340 KB |
Output is correct |
| 28 |
Correct |
2 ms |
468 KB |
Output is correct |
| 29 |
Correct |
1 ms |
364 KB |
Output is correct |
| 30 |
Correct |
1 ms |
444 KB |
Output is correct |
| 31 |
Correct |
1 ms |
408 KB |
Output is correct |
| 32 |
Correct |
1 ms |
340 KB |
Output is correct |
| 33 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
296 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
2 ms |
380 KB |
Output is correct |
| 8 |
Correct |
1 ms |
436 KB |
Output is correct |
| 9 |
Correct |
1 ms |
436 KB |
Output is correct |
| 10 |
Correct |
2 ms |
468 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
2 ms |
468 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
444 KB |
Output is correct |
| 15 |
Correct |
1 ms |
408 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
0 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
212 KB |
Output is correct |
| 23 |
Correct |
0 ms |
212 KB |
Output is correct |
| 24 |
Correct |
0 ms |
212 KB |
Output is correct |
| 25 |
Correct |
0 ms |
212 KB |
Output is correct |
| 26 |
Correct |
1 ms |
212 KB |
Output is correct |
| 27 |
Correct |
0 ms |
212 KB |
Output is correct |
| 28 |
Correct |
0 ms |
212 KB |
Output is correct |
| 29 |
Correct |
0 ms |
212 KB |
Output is correct |
| 30 |
Correct |
1 ms |
300 KB |
Output is correct |
| 31 |
Correct |
0 ms |
212 KB |
Output is correct |
| 32 |
Correct |
0 ms |
212 KB |
Output is correct |
| 33 |
Correct |
0 ms |
212 KB |
Output is correct |
| 34 |
Correct |
2 ms |
444 KB |
Output is correct |
| 35 |
Correct |
2 ms |
368 KB |
Output is correct |
| 36 |
Correct |
2 ms |
340 KB |
Output is correct |
| 37 |
Correct |
1 ms |
468 KB |
Output is correct |
| 38 |
Correct |
2 ms |
340 KB |
Output is correct |
| 39 |
Correct |
2 ms |
468 KB |
Output is correct |
| 40 |
Correct |
2 ms |
376 KB |
Output is correct |
| 41 |
Correct |
1 ms |
340 KB |
Output is correct |
| 42 |
Correct |
2 ms |
340 KB |
Output is correct |
| 43 |
Correct |
2 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
368 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
2 ms |
340 KB |
Output is correct |
| 6 |
Correct |
2 ms |
468 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
2 ms |
340 KB |
Output is correct |
| 10 |
Correct |
2 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
296 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
2 ms |
380 KB |
Output is correct |
| 18 |
Correct |
1 ms |
436 KB |
Output is correct |
| 19 |
Correct |
1 ms |
436 KB |
Output is correct |
| 20 |
Correct |
2 ms |
468 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
2 ms |
468 KB |
Output is correct |
| 23 |
Correct |
1 ms |
364 KB |
Output is correct |
| 24 |
Correct |
1 ms |
444 KB |
Output is correct |
| 25 |
Correct |
1 ms |
408 KB |
Output is correct |
| 26 |
Correct |
1 ms |
340 KB |
Output is correct |
| 27 |
Correct |
1 ms |
340 KB |
Output is correct |
| 28 |
Correct |
0 ms |
212 KB |
Output is correct |
| 29 |
Correct |
1 ms |
212 KB |
Output is correct |
| 30 |
Correct |
0 ms |
212 KB |
Output is correct |
| 31 |
Correct |
1 ms |
212 KB |
Output is correct |
| 32 |
Correct |
1 ms |
212 KB |
Output is correct |
| 33 |
Correct |
0 ms |
212 KB |
Output is correct |
| 34 |
Correct |
0 ms |
212 KB |
Output is correct |
| 35 |
Correct |
0 ms |
212 KB |
Output is correct |
| 36 |
Correct |
1 ms |
212 KB |
Output is correct |
| 37 |
Correct |
0 ms |
212 KB |
Output is correct |
| 38 |
Correct |
0 ms |
212 KB |
Output is correct |
| 39 |
Correct |
0 ms |
212 KB |
Output is correct |
| 40 |
Correct |
1 ms |
300 KB |
Output is correct |
| 41 |
Correct |
0 ms |
212 KB |
Output is correct |
| 42 |
Correct |
0 ms |
212 KB |
Output is correct |
| 43 |
Correct |
0 ms |
212 KB |
Output is correct |
| 44 |
Correct |
27 ms |
5260 KB |
Output is correct |
| 45 |
Correct |
59 ms |
4012 KB |
Output is correct |
| 46 |
Correct |
62 ms |
3964 KB |
Output is correct |
| 47 |
Correct |
62 ms |
3944 KB |
Output is correct |
| 48 |
Correct |
41 ms |
5804 KB |
Output is correct |
| 49 |
Correct |
43 ms |
6068 KB |
Output is correct |
| 50 |
Correct |
61 ms |
5524 KB |
Output is correct |
| 51 |
Correct |
60 ms |
6800 KB |
Output is correct |
| 52 |
Correct |
54 ms |
4484 KB |
Output is correct |
| 53 |
Correct |
53 ms |
3396 KB |
Output is correct |
| 54 |
Correct |
43 ms |
5912 KB |
Output is correct |
| 55 |
Correct |
43 ms |
5948 KB |
Output is correct |
