제출 #1263020

#제출 시각아이디문제언어결과실행 시간메모리
1263020kaloyanRabbit Carrot (LMIO19_triusis)C++20
0 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 10; const int INF = 1e9; int N, M; int a[MAXN]; int dp[MAXN]; int upper_binary(int x) { int l = -1, r = N; while(r > l + 1) { int m = (l + r) / 2; if(dp[m] > x) { r = m; } else { l = m; } } return r; } void solve() { cin >> N >> M; int h; for(int i = 1 ; i <= N ; ++i) { cin >> h; a[i] = M * i - h; } for(int i = 1 ; i <= N ; ++i) { dp[i] = INF; } dp[0] = -INF; for(int i = 1 ; i <= N ; ++i) { int idx = upper_binary(a[i]); dp[idx] = a[i]; } int answer = 0; for(int i = 1 ; i <= N ; ++i) { if(dp[i] < INF) { answer = i; } } cout << N - answer << "\n"; } void fastIO() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } int main() { fastIO(); 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...