제출 #424385

#제출 시각아이디문제언어결과실행 시간메모리
424385Osama_AlkhodairyFinancial Report (JOI21_financial)C++17
48 / 100
4083 ms6076 KiB
#include <bits/stdc++.h> using namespace std; #define finish(x) return cout << x << endl, 0 #define ll long long int n, d; vector <int> a; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> d; a.resize(n); for(auto &i : a) cin >> i; vector <pair <int, int> > all; for(int i = 0 ; i < n ; i++){ all.push_back(make_pair(a[i], i)); } sort(all.begin(), all.end(), [&](pair <int, int> &l, pair <int, int> &r){ return make_pair(l.first, -l.second) < make_pair(r.first, -r.second); }); set <pair <int, int> > s; vector <int> f(n); for(auto &i : all){ int idx = i.second; auto cur = make_pair(idx, idx); auto it = s.lower_bound(make_pair(idx, -1)); vector <pair <int, int> > to_erase; if(it != s.end() && idx + d >= it->first){ cur.second = it->second; to_erase.push_back(*it); } if(it != s.begin()){ it--; if(idx - d <= it->second){ cur.first = it->first; cur.second = max(cur.second, it->second); to_erase.push_back(*it); } } for(auto &j : to_erase){ s.erase(j); } f[idx] = min(cur.second + d, n - 1); s.insert(cur); } vector <int> dp(n); sort(all.begin(), all.end(), [&](pair <int, int> &l, pair <int, int> &r){ return make_pair(-l.first, l.second) < make_pair(-r.first, r.second); }); for(auto &i : all){ int idx = i.second; dp[idx] = 1; for(int j = idx + 1 ; j <= f[idx] ; j++){ dp[idx] = max(dp[idx], dp[j] + 1); } } int ans = 0; for(auto &i : dp) ans = max(ans, i); cout << ans << endl; }
#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...