Submission #743714

#TimeUsernameProblemLanguageResultExecution timeMemory
743714moonpayRabbit Carrot (LMIO19_triusis)C++17
100 / 100
28 ms8400 KiB
#include <bits/stdc++.h> #define int int64_t using namespace std; const int modm = 1e9 + 7; const int maxn = 2e3 + 5; int lis(vector<int> &a) { vector<int> dp; for (int i: a) { int pos = upper_bound(dp.begin(), dp.end(), i) - dp.begin(); if (pos == dp.size()) { dp.push_back(i); } else { dp[pos] = i; } } return dp.size(); } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> a(n + 1); a[0] = -m * n; for (int i = 0; i < n; i++) { cin >> a[i + 1]; a[i + 1] += (n - i - 1) * m; a[i + 1] *= -1; } vector<int> ne; for (auto p: a) { if (p >= a[0]) { ne.push_back(p); } } cout << n + 1 - lis(ne); }

Compilation message (stderr)

triusis.cpp: In function 'int64_t lis(std::vector<long int>&)':
triusis.cpp:13:17: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |         if (pos == dp.size()) {
      |             ~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...