# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1267820 | ducdev | Financial Report (JOI21_financial) | C++20 | 43 ms | 4680 KiB |
// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> ii;
const int MAX_N = 3e5;
const int MOD = 1e9 + 7;
template <class X, class Y>
bool maximize(X &x, const Y &y) {
if (x >= y) return false;
x = y;
return true;
};
int n, d;
int a[MAX_N + 5];
namespace SUBTASK_12 {
const int N = 400;
int dp[N + 5][N + 5];
void Solve() {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = 0;
};
};
for (int i = 1; i <= n; i++) {
dp[i][a[i]] = 1;
for (int j = i - 1; j >= max(1, i - d); j--) {
for (int mx = a[j]; mx <= n; mx++) {
maximize(dp[i][max(mx, a[i])], dp[j][mx] + (a[i] > mx));
};
};
};
int res = 0;
for (int mx = a[n]; mx <= n; mx++) maximize(res, dp[n][mx]);
cout << res << '\n';
};
}; // namespace SUBTASK_12
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen("MAIN.INP", "r")) {
freopen("MAIN.INP", "r", stdin);
freopen("MAIN.OUT", "w", stdout);
};
cin >> n >> d;
vector<ii> v(n);
for (int i = 1; i <= n; i++) {
cin >> a[i];
v[i - 1] = make_pair(a[i], i);
};
sort(all(v));
int cur = 0;
for (int i = 0; i < n; i++) {
cur += (i == 0 || v[i - 1].first != v[i].first);
a[v[i].second] = cur;
};
SUBTASK_12::Solve();
};
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |