제출 #1274850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274850		warrenn	Global Warming (CEOI18_glo)	C++20	100 / 100	112 ms	4676 KiB

glo

#include<bits/stdc++.h>
using namespace std;
#define int long long 

signed main(){
    int n,x;
    cin>>n>>x;
    int t[n+1];
    int lis[n+1];

    for(int q=1;q<=n;q++){
        cin>>t[q];
    }

    vector<int>tmp;
    for(int q=1;q<=n;q++){
        int idx=lower_bound(tmp.begin(),tmp.end(),t[q])-tmp.begin();
        if(idx==tmp.size()){
            lis[q]=tmp.size()+1;
            tmp.push_back(t[q]);
        }
        else{
            lis[q]=idx+1;
            tmp[idx]=t[q];
        }
    }
    int ans=0;
    tmp.clear();
    for(int q=n;q>=1;q--){
        int idx=lower_bound(tmp.begin(),tmp.end(),x-t[q])-tmp.begin();

        ans=max(ans,lis[q]+idx);
        ans=max(ans,lis[q]);
        idx=lower_bound(tmp.begin(),tmp.end(),-t[q])-tmp.begin();
        if(idx==tmp.size()){
            tmp.push_back(-t[q]);
        }
        else{
            tmp[idx]=-t[q];
        }
    }
    cout<<ans<<endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25