oj.uz

Submission #1087848

# Submission time Handle Problem Language Result Execution time Memory
1087848 2024-09-13T10:11:47 Z whtth Global Warming (CEOI18_glo) C++14
25 / 100
 2000 ms 3176 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 468 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 348 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 468 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 348 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 9 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 31 ms 348 KB Output is correct
15 Correct 14 ms 344 KB Output is correct
16 Correct 20 ms 472 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 468 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 348 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 9 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 31 ms 348 KB Output is correct
15 Correct 14 ms 344 KB Output is correct
16 Correct 20 ms 472 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Execution timed out 2076 ms 348 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2940 KB Output is correct
2 Correct 22 ms 2964 KB Output is correct
3 Correct 26 ms 3176 KB Output is correct
4 Correct 27 ms 3172 KB Output is correct
5 Correct 17 ms 2644 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2057 ms 1084 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 2033 ms 1624 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 468 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 348 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 9 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 31 ms 348 KB Output is correct
15 Correct 14 ms 344 KB Output is correct
16 Correct 20 ms 472 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Execution timed out 2076 ms 348 KB Time limit exceeded
20 Halted 0 ms 0 KB -