이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const ll LINF = ll(4e18) + ll(2e15);
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
static int LamyIsCute = []() {
EmiliaMyWife
return 48763;
}();
signed main() {
int n, d;
cin >> n >> d;
vector<int> arr(n), v(n);
for(int i = 0; i < n; i++) {
cin >> arr[i];
v[i] = arr[i];
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for(int &a : arr)
a = lower_bound(v.begin(), v.end(), a) - v.begin();
vector<vector<int>> dp(n, vector<int>(v.size(), -INF));
vector<int> mx(n, -INF);
for(int j = 0; j < v.size(); j++) {
deque<int> dq;
for(int i = 0; i < n; i++) {
if(j == arr[i]) {
int g = 0;
for(int k = i - 1; k >= i - d && k >= 0; k--)
g = max(g, mx[k]);
dp[i][j] = g + 1;
}
if(j >= arr[i] && i) {
while(dq.front() < i - d)
dq.pop_front();
dp[i][j] = max(dp[i][j], dp[dq.front()][j]);
}
while(!dq.empty() && dp[dq.back()][j] <= dp[i][j])
dq.pop_back();
dq.push_back(i);
}
for(int i = 0; i < n; i++)
mx[i] = max(mx[i], dp[i][j]);
}
cout << *max_element(dp.back().begin(), dp.back().end()) << '\n';
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int main()':
Main.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int j = 0; j < v.size(); j++) {
| ~~^~~~~~~~~~
# | 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... |