Submission #581601

#TimeUsernameProblemLanguageResultExecution timeMemory
581601colossal_pepeFinancial Report (JOI21_financial)C++17
65 / 100
80 ms4288 KiB
#include <iostream> #include <vector> #include <stack> using namespace std; int n, d, a[300005], dp[7005]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> d; for (int i = 0; i < n; i++) { cin >> a[i]; } if (n <= 7000) { int ans = 0; for (int i = 0; i < n; i++) { dp[i] = 1; int x = i; for (int j = i - 1; j >= max(0, x - d); j--) { if (a[j] >= a[i]) continue; x = j; dp[i] = max(dp[i], 1 + dp[j]); } ans = max(ans, dp[i]); } cout << ans << '\n'; } else if (d == 1) { int ans = 0; stack<int> s; for (int i = n - 1; i >= 0; i--) { while (not s.empty() and s.top() <= a[i]) s.pop(); s.push(a[i]); ans = max(ans, (int)s.size()); } cout << ans << '\n'; } else if (d == n) { vector<int> lis; for (int i = 0; i < n; i++) { cin >> a[i]; auto itr = lower_bound(lis.begin(), lis.end(), a[i]); if (itr == lis.end()) lis.push_back(a[i]); else lis[itr - lis.begin()] = a[i]; } cout << lis.size() << '\n'; } else { cout << "janina" << '\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...