제출 #1218272

#제출 시각아이디문제언어결과실행 시간메모리
1218272lopkusFinancial Report (JOI21_financial)C++20
0 / 100
4091 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++) { if(ord[i].first == ord[0].first) { dp[-ord[i].second] = 1; continue; } for(int j = opt[-ord[i].second]; j < -ord[i].second; j++) { dp[-ord[i].second] = std::max(dp[i], dp[j] + 1); } } for(int i = 1; i <= n; i++) { for(int j = opt[i]; j < i; j++) { if(a[i] > a[j]) { dp[i] = std::max(dp[i], 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...