Submission #1221758

#TimeUsernameProblemLanguageResultExecution timeMemory
1221758TrustfulcomicFinancial Report (JOI21_financial)C++20
65 / 100
847 ms1114112 KiB
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> ii; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,d; cin >> n >> d; vector<int> as(n); for (int& i : as) cin >> i; if (d == 1) { int maxim = 1; vector<int> stck; stck.push_back(as.back()); for (int i = as.size()-2; i>=0; i--) { while (stck.size() > 0 && stck.back() <= as[i]) stck.pop_back(); stck.push_back(as[i]); maxim = max(maxim, (int)stck.size()); } cout << maxim << endl; } else if (d == n) { vector<int> dp; dp.push_back(as[0]); for (int i = 1; i<n; i++) { int l = 0; int r = dp.size(); while (l<r) { int m = (l+r)/2; if (dp[m] < as[i]) { l = m+1; } else { r = m; } } if (l == dp.size()) { dp.push_back(as[i]); } else { dp[l] = as[i]; } } cout << dp.size() << endl; } else { vector<vector<int>> dp(n, vector<int>(n+1, -1)); vector<multiset<int>> maxs(n+1); dp[0][1] = as[0]; maxs[1].insert(as[0]); for (int i = 1; i<n; i++) { if (i > d) { // Smazat i-d-1 for (int j = 0; j<n+1; j++) { if (dp[i-d-1][j] == -1) continue; if (maxs[j].find(dp[i-d-1][j]) != maxs[j].end()) { maxs[j].erase(maxs[j].find(dp[i-d-1][j])); } } } dp[i][1] = as[i]; for (int j = 0; j<n+1; j++) { if (maxs[j].size() > 0) { int minim = *(maxs[j].begin()); if (minim < as[i]) { if (dp[i][j+1] == -1) { dp[i][j+1] = as[i]; } else { dp[i][j+1] = min(dp[i][j+1], as[i]); } } else { if (dp[i][j] == -1) { dp[i][j] = minim; } else { dp[i][j] = min(dp[i][j], minim); } } } } for (int j = 0; j<n+1; j++) { if (dp[i][j] == -1) continue; maxs[j].insert(dp[i][j]); } } int maxim = 0; for (int j = 0; j<n+1; j++) { if (dp.back()[j] != -1) maxim = j; } cout << maxim << 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...