이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <cmath>
#include <vector>
#include <iomanip>
using namespace std;
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen("revegetate.in", "r", stdin); freopen("revegetate.out", "w", stdout);
#define m_p make_pair
#define moo -1000000000000000;
#define poo 1000000000000000;
ll gcd(ll a, ll b)
{
if (a == 0 || b == 0) {
return max(a, b);
}
if (a <= b) {
return gcd(a, b % a);
}
else {
return gcd(a % b, b);
}
}
ll lcm(ll a, ll b) {
return (a / gcd(a, b)) * b;
}
const int N = 300010;
ll mx[N];
ll ans[N];
vector<pair<ll int,ll int>> dp[405];
ll int mxx[405];
ll a[N];
void solve() {
int n, d;
cin >> n >> d;
for (int i = 1;i <= n;i++) {
cin >> a[i];
}
if (d == 1) {
if (n == 1) {
cout << 1 << endl;
return;
}
ll pat = 1, l = n - 1, r = n;
mx[n] = a[n];
ans[n] = 1;
for (int i = n - 1;i >= 1;i--) {
ll kk = n + 1;
r = n;
// cout << i << " " << l << " " << r << endl;
while (l <= r) {
ll mid = (l + r) / 2;
//cout << i << " " << mid << " " << mx[mid] << endl;
if (mx[mid] > a[i]) {
kk = mid;
r = mid-1;
}
else {
l = mid+1;
}
}
//cout << kk << " " << i << endl;
if (kk != n + 1) {
pat = max(ans[kk]+1, pat);
ans[kk - 1] = ans[kk] + 1;
mx[kk-1] = a[i];
l = kk-1;
}
else {
l = n;
ans[l] = 1;
mx[l] = a[i];
}
}
cout << pat << endl;
return;
}
if (n <= 400) {
if (n == 1) {
cout << 1 << endl;
return;
}
dp[1].push_back({ a[1],1 });
mxx[1] = 1;
map<ll, ll> mp;
vector<ll> v;
for (int i = 2;i <= n;i++) {
for (int j = max(i - d,1);j < i;j++) {
for (int k = 0;k < dp[j].size();k++) {
if (dp[j][k].fr < a[i]) {
if (mp[a[i]] == 0) {
v.pb(a[i]);
}
mp[a[i]] = max(mp[a[i]], dp[j][k].sc + 1);
}
else {
if (mp[dp[j][k].fr] == 0) {
v.pb(dp[j][k].fr);
}
mp[dp[j][k].fr] = max(mp[dp[j][k].fr], dp[j][k].sc);
}
}
}
if (mp[a[i]] == 0) {
v.pb(a[i]);
}
mp[a[i]] = max(mp[a[i]],1LL);
for (int j = 0;j < v.size();j++) {
dp[i].push_back({ v[j],mp[v[j]] });
mxx[i] = max(mxx[i], mp[v[j]]);
}
mp.clear();
v.clear();
}
cout << mxx[n] << endl;
}
/*for (int i = 1;i <= n;i++) {
if (i > d) {
for (int j = i - d;j < i;j++) {
int l = 0;
int r = dp[j].size() - 1, ind = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (dp[j][mid].fr < a[i]) {
ind = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
if (ind != -1) {
if (sum[ind] + 1 > mx) {
mx = sum[ind] + 1;
}
}
else {
for (int jj = 0;jj < dp[j].size();jj++) {
dp[i].push_back({ dp[j][jj].fr,dp[j][jj].sc });
}
}
}
if (mx != -1) {
dp[i].pb({ mx,a[i] });
}
sort(dp[i].begin(), dp[i].end());
}
else {
}
}*/
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
//US
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'void solve()':
Main.cpp:112:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for (int k = 0;k < dp[j].size();k++) {
| ~~^~~~~~~~~~~~~~
Main.cpp:131:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | 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... |