Submission #1274380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274380		warrenn	Global Warming (CEOI18_glo)	C++20	42 / 100	80 ms	6796 KiB

glo

#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();
}

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<=50 && x<=50){
        int ans=0;
        for(int val=-x;val<=x;val++){
            for(int l=0;l<n;l++){
                for(int r=l;r<n;r++){
                    a[r]+=val;
                    ans=max(ans,lis(a));
                }
                for(int r=l;r<n;r++){
                    a[r]-=val;
                }
            }
        }
        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;
    }
}

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