Submission #1087848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087848		whtth	Global Warming (CEOI18_glo)	C++14	25 / 100	2076 ms	3176 KiB

glo

#include<bits/stdc++.h>
using namespace std;
int n, m, d, k, ans=1, f[501][501], a[200001], s[200001];
void sub12(){
    for(int x=-m;x<=m;x++){
        for(int l=1;l<=n;l++){
            for(int r=l;r<=n;r++){
                int now, cnt=1;
                if(l<=1 and 1<=r)now=a[1]-x;
                else now=a[1];
                s[cnt]=now;
                for(int i=2;i<=n;i++){
                    if(l<=i and i<=r)now=a[i]-x;
                    else now=a[i];
                    int l=1, r=cnt, vt=0;
                    while(l<=r){
                        int mid=(l+r)/2;
                        if(s[mid]<now){
                            vt=mid;
                            l=mid+1;
                        }
                        else r=mid-1;
                    }
                    if(vt==cnt)cnt++, s[cnt]=1e9+1;
                    s[vt+1]=min(s[vt+1], now);
                }
                ans=max(ans, cnt);
            }
        }
    }
    cout<<ans;
}
void sub0(){
    int now, cnt=1, l=1, r=n;
    now=a[1];
    s[cnt]=now;
    for(int i=2;i<=n;i++){
        now=a[i];
        int l=1, r=cnt, vt=0;
        while(l<=r){
            int mid=(l+r)/2;
            if(s[mid]<now){
                vt=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        if(vt==cnt)cnt++, s[cnt]=1e9+1;
        s[vt+1]=min(s[vt+1], now);
    }
    cout<<cnt;
}
void sub3(){

}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("glo.inp", "r", stdin);
    //freopen("glo.out", "w", stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    if(m==0)sub0();
    else sub12();
    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'void sub0()':
glo.cpp:34:21: warning: unused variable 'l' [-Wunused-variable]
   34 |     int now, cnt=1, l=1, r=n;
      |                     ^
glo.cpp:34:26: warning: unused variable 'r' [-Wunused-variable]
   34 |     int now, cnt=1, l=1, r=n;
      |                          ^

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