제출 #1221745

#제출 시각아이디문제언어결과실행 시간메모리
1221745TrustfulcomicFinancial Report (JOI21_financial)C++20
48 / 100
853 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; 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...