Submission #1218273

#TimeUsernameProblemLanguageResultExecution timeMemory
1218273lopkusFinancial Report (JOI21_financial)C++20
48 / 100
4094 ms9904 KiB
#include <bits/stdc++.h> #define int int64_t void solve() { int n, d; std::cin >> n >> d; std::vector<int> a(n + 1); for(int i = 1; i <= n; i++) { std::cin >> a[i]; } std::vector<int> compres; for(int i = 1; i <= n; i++) { compres.push_back(a[i]); } std::sort(compres.begin(), compres.end()); for(int i = 1; i <= n; i++) { a[i] = lower_bound(compres.begin(), compres.end(), a[i]) - compres.begin() + 1; } std::vector<int> dp(n + 1, 0); std::vector<int> opt(n + 1, 1); for(int i = 1; i <= n; i++) { int prv = i; for(int j = i - 1; j >= 1; j--) { if(prv - j > d) { opt[i] = j + 1; break; } if(a[j] <= a[i]) { prv = j; } } } std::vector<std::pair<int, int>> ord; for(int i = 1; i <= n; i++) { ord.push_back({a[i], - i}); } std::sort(ord.begin(), ord.end()); for(int i = 0; i < n; i++) { dp[-ord[i].second] = 1; for(int j = opt[-ord[i].second]; j < -ord[i].second; j++) { dp[-ord[i].second] = std::max(dp[-ord[i].second], dp[j] + 1); } } std::cout << *max_element(dp.begin() + 1, dp.end()); } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t = 1; //std::cin >> t; while (t--) { solve(); } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...