oj.uz

Submission #1096278

# Submission time Handle Problem Language Result Execution time Memory
1096278 2024-10-04T07:47:31 Z trinhvtuan Global Warming (CEOI18_glo) C++17
10 / 100
 2000 ms 262152 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 396 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 396 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 396 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 6860 KB Output is correct
2 Correct 117 ms 6820 KB Output is correct
3 Correct 113 ms 6860 KB Output is correct
4 Correct 112 ms 6776 KB Output is correct
5 Correct 57 ms 4876 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2425 ms 262152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2604 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 396 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -