제출 #1218268

#제출 시각아이디문제언어결과실행 시간메모리
1218268benrRabbit Carrot (LMIO19_triusis)C++20
100 / 100
55 ms6584 KiB
#include <bits/stdc++.h> using namespace std; int n, m; int lds (vector<long long> &a) { for (int i = 0; i < a.size(); i++) a[i] *= -1; // now we can do lis vector<long long> dp; // smallest last number for each increasing subsequence length for (int i = 0; i < a.size(); i++) { int position = upper_bound(dp.begin(), dp.end(), a[i]) - dp.begin(); if (position == dp.size()) { dp.push_back(a[i]); } else { dp[position] = a[i]; } } return dp.size(); } int main() { cin >> n >> m; vector<long long> bridge (n); vector<long long> nochange; for (int i = 0; i < n; i++) { cin >> bridge[i]; bridge[i] -= m * (i + 1); // makes it so bunnies jump is 0 if (bridge[i] <= 0) nochange.push_back(bridge[i]); } cout << n - lds(nochange); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...