이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << '\n')
#define PV2(x) DEBUG(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << " "); PRINT("}\n");)
typedef int64_t i64;
const int INF = 1000000007; //998244353;
struct S {
i64 n, k;
vector<i64> a, b;
void run() {
cin >> n >> k;
a.resize(n); b.resize(n, k);
for (int i = 0; i < n; ++i) {
cin >> a[i];
b[i] += a[i];
}
reverse(b.begin(), b.end());
PAR(a); PAR(b);
vector<i64> lis;
vector<pair<i64, i64>> dpa(n); // {location, old val}
for (int i = 0; i < n; ++i) {
i64 pos = lower_bound(lis.begin(), lis.end(), a[i]) - lis.begin();
if (pos == lis.size()) {
dpa[i] = {pos, -1};
lis.push_back(a[i]);
} else {
dpa[i] = {pos, lis[pos]};
lis[pos] = a[i];
}
}
PAR(lis);
reverse(dpa.begin(), dpa.end());
PAR2(dpa);
i64 ans = lis.size();
vector<i64> lds;
for (int i = 0; i < n; ++i) {
lis[dpa[i].first] = dpa[i].second;
if (lis[dpa[i].first] == -1) lis.pop_back();
// find first element smaller than b[i]
i64 pos = lower_bound(lds.begin(), lds.end(), -b[i]) - lds.begin();
PV(pos);
if (pos == lds.size()) {
lds.push_back(-b[i]);
} else {
lds[pos] = -b[i];
}
i64 bad = (lis.size() ? lds.end() - lower_bound(lds.begin(), lds.end(),
-lis.back()) : 0);
PV(bad);
ans = max(ans, i64(lis.size() + lds.size() - bad));
PAR(lis);
PAR(lds);
PV(ans);
}
cout << ans << '\n';
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
auto sol = make_unique<S>();
sol->run();
}
컴파일 시 표준 에러 (stderr) 메시지
glo.cpp: In member function 'void S::run()':
glo.cpp:31:15: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | if (pos == lis.size()) {
| ~~~~^~~~~~~~~~~~~
glo.cpp:52:15: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | if (pos == lds.size()) {
| ~~~~^~~~~~~~~~~~~
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |