// Author : Zobin Singh (Chotu)
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pb push_back
#define mp make_pair
#define fl(i, a, b) for (int i = a; i < b; i++)
#define vi vector<int>
#define all(v) v.begin(),v.end()
#define e1(a) \
int a; \
cin >> a;
#define e2(a, b) \
int a, b; \
cin >> a >> b;
#define e3(a, b, c) \
int a, b, c; \
cin >> a >> b >> c;
#define av(arr, n) \
vector<int> arr(n); \
fl(i, 0, n) cin >> arr[i];
#define aa(arr, n) \
int arr[n]; \
fl(i, 0, n) cin >> arr[i];
#define es(s) \
string(s); \
cin >> (s);
#define vi vector<int>
#define vvi vector<vector<int>>
#define mod 1000000007
#define ff first
#define ss second
#define inf 10e15
#define pii pair<int, int>
#define mii map<int, int>
#define vl(n) cout << n << "\n"
#define vs(n) cout << n << " "
#define el cout << "\n"
#define UB upper_bound
#define LB lower_bound
#define vn(n) cout << n
#define dsc greater<int>()
#define ps(x, y) fixed << setprecision(y) << x
#define R return
#define livu_sz ios_base::sync_with_stdio(false);
#define vsingh cin.tie(NULL);
#define B break
#define C continue
int dmod(int x) {
return ((x + mod) % mod);
}
int power(int x, int y)
{
int res = 1;
while (y)
{
if (y & 1) res = (res * x) % mod;
x = (x * x) % mod; y >>= 1;
}
return res;
}
#define YC cout << "YES" \
<< "\n"
#define YS cout << "Yes" \
<< "\n"
#define NC cout << "NO" \
<< "\n"
#define NS cout << "No" \
<< "\n"
#define lcm(a, b) (a / __gcd(a, b)) * b
#define pa(a) \
for (auto e : a) \
cout << e << " "
const int N = 1e6;
int dx[4] = { -1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
#ifndef ONLINE_JUDGE
#define pra(a, n) \
cerr << #a << ":"; \
for (int i = 0; i < n; i++) \
cerr << a[i] << " "; \
cerr << endl;
#define prm(mat, row, col) \
cerr << #mat << ":\n"; \
for (int i = 0; i < row; i++) \
{ \
for (int j = 0; j < col; j++) \
cerr << mat[i][j] << " "; \
cerr << endl; \
}
#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
template <class S, class T>
ostream &operator<<(ostream &os, const pair<S, T> &p)
{
return os << "(" << p.first << "," << p.second << ")";
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &p)
{
os << "[";
for (auto &it : p)
os << it << " ";
return os << "]";
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &p)
{
os << "[";
for (auto &it : p)
os << it << " ";
return os << "]";
}
template <class T>
ostream &operator<<(ostream &os, const multiset<T> &p)
{
os << "[";
for (auto &it : p)
os << it << " ";
return os << "]";
}
template <class S, class T>
ostream &operator<<(ostream &os, const map<S, T> &p)
{
os << "[";
for (auto &it : p)
os << it << " ";
return os << "]";
}
template <class T>
void dbs(string str, T t) { cerr << str << ":" << t << "\n"; }
template <class T, class... S>
void dbs(string str, T t, S... s)
{
int idx = str.find(',');
cerr << str.substr(0, idx) << ":" << t << ",";
dbs(str.substr(idx + 1), s...);
}
#else
#define pr(...) \
{ \
}
#define pra(a, n) \
{ \
}
#define prm(mat, row, col) \
{ \
}
#endif
// I can and I will : LIVU
// Template ends
void solve()
{
e2(n,m);
int a[n+1];
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
pra(a,n+1);
vector<int>ans;
for(int i=1;i<=n;i++)
{
if(ans.size()==0)
{
if(m*i>=a[i])
{
ans.pb(m*i - a[i]);
}
}
else
{
if(m*i-a[i]>=ans.back() && m*i>=a[i])
{
ans.pb(m*i-a[i]);
}
else if(m*i>=a[i])
{
auto it=UB(all(ans),m*i-a[i]);
*it=(m*i-a[i]);
}
}
}
// pr(ans);
cout<<n-ans.size()<<endl;
}
int32_t main()
{
livu_sz
vsingh
int t = 1;
// cin>>t;
while (t--)
solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 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 |
0 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 |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 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 |
0 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 |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
320 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
10 ms |
368 KB |
Output is correct |
21 |
Correct |
12 ms |
468 KB |
Output is correct |
22 |
Correct |
13 ms |
340 KB |
Output is correct |
23 |
Correct |
14 ms |
392 KB |
Output is correct |
24 |
Correct |
13 ms |
468 KB |
Output is correct |
25 |
Correct |
16 ms |
460 KB |
Output is correct |
26 |
Correct |
13 ms |
404 KB |
Output is correct |
27 |
Correct |
12 ms |
400 KB |
Output is correct |
28 |
Correct |
12 ms |
400 KB |
Output is correct |
29 |
Correct |
13 ms |
456 KB |
Output is correct |
30 |
Correct |
12 ms |
468 KB |
Output is correct |
31 |
Correct |
14 ms |
468 KB |
Output is correct |
32 |
Correct |
13 ms |
404 KB |
Output is correct |
33 |
Correct |
13 ms |
396 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 |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
10 ms |
368 KB |
Output is correct |
5 |
Correct |
12 ms |
468 KB |
Output is correct |
6 |
Correct |
13 ms |
340 KB |
Output is correct |
7 |
Correct |
14 ms |
392 KB |
Output is correct |
8 |
Correct |
13 ms |
468 KB |
Output is correct |
9 |
Correct |
16 ms |
460 KB |
Output is correct |
10 |
Correct |
13 ms |
404 KB |
Output is correct |
11 |
Correct |
12 ms |
400 KB |
Output is correct |
12 |
Correct |
12 ms |
400 KB |
Output is correct |
13 |
Correct |
13 ms |
456 KB |
Output is correct |
14 |
Correct |
12 ms |
468 KB |
Output is correct |
15 |
Correct |
14 ms |
468 KB |
Output is correct |
16 |
Correct |
13 ms |
404 KB |
Output is correct |
17 |
Correct |
13 ms |
396 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 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 |
0 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 |
1 ms |
212 KB |
Output is correct |
30 |
Correct |
1 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 |
1 ms |
320 KB |
Output is correct |
34 |
Correct |
13 ms |
340 KB |
Output is correct |
35 |
Correct |
13 ms |
340 KB |
Output is correct |
36 |
Correct |
12 ms |
452 KB |
Output is correct |
37 |
Correct |
12 ms |
468 KB |
Output is correct |
38 |
Correct |
14 ms |
440 KB |
Output is correct |
39 |
Correct |
15 ms |
432 KB |
Output is correct |
40 |
Correct |
13 ms |
388 KB |
Output is correct |
41 |
Correct |
14 ms |
396 KB |
Output is correct |
42 |
Correct |
12 ms |
408 KB |
Output is correct |
43 |
Correct |
13 ms |
400 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
340 KB |
Output is correct |
2 |
Correct |
13 ms |
340 KB |
Output is correct |
3 |
Correct |
12 ms |
452 KB |
Output is correct |
4 |
Correct |
12 ms |
468 KB |
Output is correct |
5 |
Correct |
14 ms |
440 KB |
Output is correct |
6 |
Correct |
15 ms |
432 KB |
Output is correct |
7 |
Correct |
13 ms |
388 KB |
Output is correct |
8 |
Correct |
14 ms |
396 KB |
Output is correct |
9 |
Correct |
12 ms |
408 KB |
Output is correct |
10 |
Correct |
13 ms |
400 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
10 ms |
368 KB |
Output is correct |
15 |
Correct |
12 ms |
468 KB |
Output is correct |
16 |
Correct |
13 ms |
340 KB |
Output is correct |
17 |
Correct |
14 ms |
392 KB |
Output is correct |
18 |
Correct |
13 ms |
468 KB |
Output is correct |
19 |
Correct |
16 ms |
460 KB |
Output is correct |
20 |
Correct |
13 ms |
404 KB |
Output is correct |
21 |
Correct |
12 ms |
400 KB |
Output is correct |
22 |
Correct |
12 ms |
400 KB |
Output is correct |
23 |
Correct |
13 ms |
456 KB |
Output is correct |
24 |
Correct |
12 ms |
468 KB |
Output is correct |
25 |
Correct |
14 ms |
468 KB |
Output is correct |
26 |
Correct |
13 ms |
404 KB |
Output is correct |
27 |
Correct |
13 ms |
396 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
0 ms |
212 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 |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
0 ms |
212 KB |
Output is correct |
36 |
Correct |
0 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 |
1 ms |
212 KB |
Output is correct |
40 |
Correct |
1 ms |
212 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
42 |
Correct |
1 ms |
212 KB |
Output is correct |
43 |
Correct |
1 ms |
320 KB |
Output is correct |
44 |
Correct |
472 ms |
4924 KB |
Output is correct |
45 |
Correct |
486 ms |
5728 KB |
Output is correct |
46 |
Correct |
482 ms |
5884 KB |
Output is correct |
47 |
Correct |
496 ms |
5752 KB |
Output is correct |
48 |
Correct |
468 ms |
5932 KB |
Output is correct |
49 |
Correct |
470 ms |
6420 KB |
Output is correct |
50 |
Correct |
488 ms |
6984 KB |
Output is correct |
51 |
Correct |
482 ms |
7892 KB |
Output is correct |
52 |
Correct |
486 ms |
4960 KB |
Output is correct |
53 |
Correct |
472 ms |
4352 KB |
Output is correct |
54 |
Correct |
468 ms |
6180 KB |
Output is correct |
55 |
Correct |
478 ms |
6212 KB |
Output is correct |