이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 3e5 + 7, N2 = 400 + 2;
int n, d;
int a[N];
int b[N];
void compress() {
copy(a + 1, a + n + 1, b + 1);
sort(b + 1, b + n + 1);
for (int i = 1; i <= n; ++i)
a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
}
// dp[i][j] -> dp[k][max(j, a[k])]
// j < a[k] : dp[k][a[k]] <- dp[i][j] + 1
// => dp[k][a[k]] <- max(dp[i][a[k] - 1], ..., dp[i][0]) + 1
// j >= a[k] : dp[k][ j ] <- dp[i][j]
//
// dp[i][j] -> dp[k][a[j] > a[k] ? j : k]
void maximize(int &a, int b) { if (a < b) a = b; }
int dp[N2][N2];
void subtask2() {
for (int i = 0; i < n; ++i)
for (int j = 0; j <= i; ++j)
for (int k = i + 1; k <= min(n, i + d); ++k) {
if (a[j] < a[k])
maximize(dp[k][k], dp[i][j] + 1);
else maximize(dp[k][j], dp[i][j]);
}
int ans(0);
for (int i = 1; i <= n; ++i)
maximize(ans, dp[n][i]);
cout << ans << '\n';
}
int L[N], cnt[N];
int st[N], top;
void subtask4() {
for (int i = 1; i <= n; ++i) {
while (top && st[top] < a[i]) --top;
++cnt[L[i] = st[top]];
st[++top] = i;
}
int ans(0), sum(1);
for (int i = 0; i < n; ++i) {
sum += cnt[i] - 1;
ans = max(ans, sum);
}
cout << ans << '\n';
}
int main() {
cin.tie(NULL)->sync_with_stdio(false);
cin >> n >> d;
for (int i = 1; i <= n; ++i) cin >> a[i];
compress();
if (n <= 400) subtask2();
else if (d == 1) subtask4();
}
/** /\_/\
* (= ._.)
* / >0 \>1
**/
# | 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... |