Submission #164091

#	Time	Username	Problem	Language	Result	Execution time	Memory
164091		errorgorn	Global Warming (CEOI18_glo)	C++14	15 / 100	834 ms	3224 KiB

glo

#include <cstdio>
#include <vector>
using namespace std;
int n,k;
int arr[200005];

int test(int i){
    vector<int> v;
    vector<int>::iterator it;
    v.push_back(arr[0]);
    for (int x=1;x<i;x++){
        if (v.back()<arr[x]) v.push_back(arr[x]);
        else{
            it=lower_bound(v.begin(),v.end(),arr[x]);
            v[it-v.begin()]=arr[x];
        }
    }
    for (int x=i;x<n;x++){
        if (v.back()<arr[x]+k) v.push_back(arr[x]+k);
        else{
            it=lower_bound(v.begin(),v.end(),arr[x]+k);
            v[it-v.begin()]=arr[x]+k;
        }
    }

    return v.size();
}

int main(){
    scanf("%d%d",&n,&k);
    for (int x=0;x<n;x++) scanf("%d",&arr[x]);

    int s=1,e=n;
    int t1,t2;
    int v1,v2;
    while (e-s>3){
        t1=s+(e-s)/3;
        t2=s+(e-s)*2/3;
        v1=test(t1);
        v2=test(t2);
        if (v1>v2){
            e=t2;
        }
        else{
            s=t1;
        }
    }
    int best=-1;
    for (int x=s;x<=e;x++){
        best=max(best,test(x));
    }

    printf("%d\n",best);
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~
glo.cpp:31:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int x=0;x<n;x++) scanf("%d",&arr[x]);
                           ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 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