Submission #1096278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096278		trinhvtuan	Global Warming (CEOI18_glo)	C++17	10 / 100	2604 ms	262152 KiB

glo

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define li pair<ll,int>
#define i2 pair<int,int>
using namespace std;
int n;
ll a[200003],x;int st[800003];
ll f[2003][2003][3][2];
vector<int> rr;
ll dp(int id,int trc,int dc,bool co){
    if (id>n){
        return 0;
    }
    if (f[id][trc][dc][co]!=-1) return f[id][trc][dc][co];
    ll ans=-1e15;
    if (dc==1){
        if (a[id]>a[trc]) ans=max(ans,dp(id+1,id,dc,1)+1);
        if (a[id]>a[trc]-x) ans=max(ans,dp(id+1,id,2,0)+1);
        ans=max(ans,dp(id+1,trc,2,1));
    }
    if (dc==0){
        if (a[id]>a[trc]) ans=max(ans,dp(id+1,id,0,0)+1);
        if (a[id]-x>a[trc]) ans=max(ans,dp(id+1,id,1,1)+1);
        ans=max(ans,dp(id+1,trc,dc,co));
    }
    if (dc==2){
        if (a[id]>a[trc]&&co==0) ans=max(ans,dp(id+1,id,dc,co)+1);
        if (a[id]>a[trc]-x&&co==1) ans=max(ans,dp(id+1,id,dc,0)+1);
        ans=max(ans,dp(id+1,trc,dc,co));
    }
    return f[id][trc][dc][co]=ans;
}
ll dp_1(int id,int trc,int dc,bool co){
    if (id>n){
        return 0;
    }
    if (f[id][trc][dc][co]!=-1) return f[id][trc][dc][co];
    ll ans=-1e15;
    if (dc==1){
        if (a[id]>a[trc]) ans=max(ans,dp_1(id+1,id,dc,1)+1);
        if (a[id]>a[trc]+x) ans=max(ans,dp_1(id+1,id,2,0)+1);
        ans=max(ans,dp_1(id+1,trc,2,1));
    }
    if (dc==0){
        if (a[id]>a[trc]) ans=max(ans,dp_1(id+1,id,0,0)+1);
        if (a[id]+x>a[trc]) ans=max(ans,dp_1(id+1,id,1,1)+1);
        ans=max(ans,dp_1(id+1,trc,dc,co));
    }
    if (dc==2){
        if (a[id]>a[trc]&&co==0) ans=max(ans,dp_1(id+1,id,dc,co)+1);
        if (a[id]>a[trc]+x&&co==1) ans=max(ans,dp_1(id+1,id,dc,0)+1);
        ans=max(ans,dp_1(id+1,trc,dc,co));
    }
    return f[id][trc][dc][co]=ans;
}
void update(int id,int l,int r,int i,int x){
    if (i<l||r<i) return;
    if (l==r){
        st[id]=x;
        return;
    }
    int mid=l+r>>1;
    update(id*2,l,mid,i,x);
    update(id*2+1,mid+1,r,i,x);
    st[id]=max(st[id*2],st[id*2+1]);
}
int get(int id,int l,int r,int u,int v){
    if (v<l||r<u) return 0;
    if (u<=l&&r<=v) return st[id];
    int mid=l+r>>1;
    return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("DAYDEP.inp","r",stdin);
    //freopen("DAYDEP.out","w",stdout);
    cin>>n>>x;
    for (int i=1;i<=n;i++) {cin>>a[i];rr.push_back(a[i]);}
    if (x==0){
        sort(rr.begin(),rr.end());
        auto k=unique(rr.begin(),rr.end());
        rr.erase(k,rr.end());
        int lim=rr.size();
        for (int i=1;i<=n;i++) a[i]=lower_bound(rr.begin(),rr.end(),a[i])-rr.begin()+1;
        for (int i=1;i<=n;i++){
            int k=(a[i]>1?get(1,1,lim,1,a[i]-1):0);
            update(1,1,lim,a[i],k+1);
        }
        cout<<get(1,1,lim,1,lim);
    }
    else {
        for (int i=1;i<=n;i++){
            for (int j=0;j<=n;j++){
                for (int k=0;k<3;k++){
                    f[i][j][k][0]=f[i][j][k][1]=-1;
                }
            }
        }
        ll kq=dp_1(1,0,0,0);
        for (int i=1;i<=n;i++){
            for (int j=0;j<=n;j++){
                for (int k=0;k<3;k++){
                    f[i][j][k][0]=f[i][j][k][1]=-1;
                }
            }
        }
        cout<<max(kq,dp(1,0,0,0));
    }
    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'void update(int, int, int, int, int)':
glo.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     int mid=l+r>>1;
      |             ~^~
glo.cpp: In function 'int get(int, int, int, int, int)':
glo.cpp:72:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |     int mid=l+r>>1;
      |             ~^~

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