Submission #164091

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
164091	2019-11-17T12:38:57 Z	errorgorn	Global Warming (CEOI18_glo)	C++14	15 / 100	834 ms	3224 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	380 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	256 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct

Subtask #2

0 / 10.0

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

Subtask #3

0 / 13.0

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

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	826 ms	3060 KB	Output is correct
2	Correct	824 ms	3164 KB	Output is correct
3	Correct	834 ms	3064 KB	Output is correct
4	Correct	815 ms	3192 KB	Output is correct
5	Correct	239 ms	3224 KB	Output is correct

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	167 ms	1016 KB	Output is correct
2	Correct	173 ms	1024 KB	Output is correct
3	Correct	175 ms	988 KB	Output is correct
4	Incorrect	51 ms	1096 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #6

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	356 ms	1728 KB	Output is correct
2	Incorrect	350 ms	1756 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

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