제출 #788760

#제출 시각아이디문제언어결과실행 시간메모리
788760Desh03Financial Report (JOI21_financial)C++17
5 / 100
2703 ms288764 KiB
#include <bits/stdc++.h> using namespace std; struct Fenwick { vector<multiset<int>> F; int n; Fenwick(int n_) : n(n_) { F.resize(n); } void remove(int x, int d) { for (; x < n; x |= x + 1) F[x].erase(F[x].find(d)); } void add(int x, int d) { for (; x < n; x |= x + 1) F[x].insert(d); } int qry(int x) { int s = 0; for (; x >= 0; x = (x & (x + 1)) - 1) if (F[x].size()) s = max(s, *F[x].rbegin()); return s; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, d; cin >> n >> d; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector<int> v = a; sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); for (int &x : a) x = lower_bound(v.begin(), v.end(), x) - v.begin(); Fenwick fen(n); vector<int> dp(n); for (int i = 0; i < n; i++) { dp[i] = fen.qry(a[i] - 1) + 1; fen.add(a[i], dp[i]); if (i >= d) fen.remove(a[i - d], dp[i - d]); } cout << *max_element(dp.begin(), dp.end()) << '\n'; 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...