Submission #1194325

#TimeUsernameProblemLanguageResultExecution timeMemory
1194325marcus06Rabbit Carrot (LMIO19_triusis)C++20
100 / 100
17 ms2244 KiB
#include <bits/stdc++.h> using namespace std; using lli = long long; #ifdef LOCAL #include </home/marcus06/mycp/Library/debug.h> #else #define debug(...) #endif void solve() { int N, M; cin >> N >> M; vector <int> A(N); for (int i = 0; i < N; ++i) { cin >> A[i]; A[i] = (i + 1) * M - A[i]; } vector <int> lis = {0}; for (int i = 0; i < N; ++i) { if (A[i] < 0) continue; auto it = upper_bound(lis.begin(), lis.end(), A[i]); if (it == lis.end()) { lis.push_back(A[i]); } else { *it = A[i]; } } cout << N - int(lis.size()) + 1 << '\n'; } int main() { std::cin.tie(0)->sync_with_stdio(0); #ifdef LOCAL auto begin = std::chrono::high_resolution_clock::now(); #endif int tt = 1; while (tt--) { solve(); } #ifdef LOCAL auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); std::cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; #endif return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...