#include<bits/stdc++.h>
using namespace std;
#define int long long
int lis(vector<int>&a){
vector<int>tmp;
for(int q=0;q<a.size();q++){
int id=lower_bound(tmp.begin(),tmp.end(),a[q])-tmp.begin();
if(id==tmp.size()){
tmp.push_back(a[q]);
}
else{
tmp[id]=a[q];
}
}
return tmp.size();
}
int pref[1000+2][42],suf[1000+2][42];
signed main(){
int n,x;
cin>>n>>x;
vector<int>a;
for(int q=0;q<n;q++){
int x;
cin>>x;
a.push_back(x);
}
if(n<=1000){
for(int q=0;q<=1001;q++){
for(int w=0;w<=42;w++){
pref[q][w]=1e18;
suf[q][w]=-1e18;
}
}
pref[0][0]=0;
for(int q=1;q<=n;q++){
for(int l=0;l<q;l++){
pref[q][l]=min(pref[q][l],pref[q-1][l]);
if(a[q-1]>pref[q-1][l]){
pref[q][l+1]=min(pref[q][l+1],a[q-1]);
}
}
}
suf[n+1][0]=1e18;
for(int q=n;q>=1;q--){
for(int l=0;l<=n-q+1;l++){
suf[q][l]=max(suf[q][l],suf[q+1][l]);
if(a[q-1]<suf[q+1][l]){
suf[q][l+1]=max(suf[q][l+1],a[q-1]);
}
}
}
int ans=0;
for(int q=1;q<=n;q++){
vector<int>tmp;
for(int w=n;w>=0;w--){
tmp.push_back(suf[q+1][w]);
}
for(int w=0;w<=q;w++){
if(pref[q][w]!=1e18){
int id=upper_bound(tmp.begin(),tmp.end(),pref[q][w]-x)-tmp.begin();
ans=max(ans,w+(int)tmp.size()-1-id);
}
}
}
cout<<ans<<endl;
}
else if(x==0){
cout<<lis(a)<<endl;
}
else if(x==1e9){
int lis[n+1];
lis[0]=0;
vector<int>tmp;
for(int q=1;q<=n;q++){
int id=lower_bound(tmp.begin(),tmp.end(),a[q-1])-tmp.begin();
if(id==tmp.size()){
tmp.push_back(a[q-1]);
}
else{
tmp[id]=a[q-1];
}
lis[q]=tmp.size();
}
tmp.clear();
int lds[n+2]; lds[n+1]=0;
for(int q=n;q>=1;q--){
int id=lower_bound(tmp.begin(),tmp.end(),-a[q-1])-tmp.begin();
if(id==tmp.size()){
tmp.push_back(-a[q-1]);
}
else{
tmp[id]=-a[q-1];
}
lds[q]=tmp.size();
}
int ans=0;
for(int q=1;q<=n;q++){
ans=max(ans,lis[q]+lds[q+1]);
}
cout<<ans<<endl;
}
}
컴파일 시 표준 에러 (stderr) 메시지
glo.cpp: In function 'int main()':
glo.cpp:34:27: warning: iteration 42 invokes undefined behavior [-Waggressive-loop-optimizations]
34 | pref[q][w]=1e18;
| ~~~~~~~~~~^~~~~
glo.cpp:33:26: note: within this loop
33 | for(int w=0;w<=42;w++){
| ~^~~~
# | 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... |