oj.uz

Submission #395801

# Submission time Handle Problem Language Result Execution time Memory
395801 2021-04-29T00:40:23 Z Pichon5 Global Warming (CEOI18_glo) C++17
28 / 100
 2000 ms 5700 KB 
#include<bits/stdc++.h>
#include <chrono>
#include <thread>
#define lcm(a,b) (a/__gcd(a,b))*b
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
#define mp make_pair
//salida rapida "\n"
//DECIMALES fixed<<sp(n)<<x<<endl;
//gcd(a,b)= ax + by
//lCB x&-x
//set.erase(it) - ersases the element present at the required index//auto it = s.find(element)
//set.find(element) - iterator pointing to the given element if it is present else return pointer pointing to set.end()
//set.lower_bound(element) - iterator pointing to element greater than or equal to the given element
//set.upper_bound(element) - iterator pointing to element greater than the given element
// | ^
//__builtin_popcount(x)
using namespace std;

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
const ll inf=1e16;

int main()
{
    int n,k;
    cin>>n>>k;
    vll a(n+2);
    vll d;
    vll aux;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int res=0;
    aux=a;
    for(int j=n;j>=0;j--){
            a[j]+=k;
                d.assign(n+2,inf);
                d[0]=-inf;
               for(int i=0;i<n;i++){
                int b=1,e=n;
                while(b<=e){
                    int mid=(b+e)/2;
                    if(a[i]<d[mid] && a[i]>d[mid-1]){
                    d[mid]=a[i];
                    break;
                }
                if(d[mid]>a[i]){
                    e=mid-1;
                }else{
                    b=mid+1;
                }
            }
            for(int i=1;i<=n;i++){
                if(d[i]!=inf){
                    res=max(res,i);
                }
            }
        }
    }
    cout<<res<<endl;
    return 0;
}
//409336628

Compilation message

glo.cpp:26: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   26 | #pragma GCC optimization ("O3")
      | 
glo.cpp:27: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   27 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1014 ms 304 KB Output is correct
20 Correct 1016 ms 324 KB Output is correct
21 Correct 1000 ms 308 KB Output is correct
22 Correct 1004 ms 324 KB Output is correct
23 Correct 1055 ms 324 KB Output is correct
24 Correct 1048 ms 324 KB Output is correct
25 Correct 794 ms 296 KB Output is correct
26 Correct 1040 ms 304 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 1996 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 2070 ms 3396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1014 ms 304 KB Output is correct
20 Correct 1016 ms 324 KB Output is correct
21 Correct 1000 ms 308 KB Output is correct
22 Correct 1004 ms 324 KB Output is correct
23 Correct 1055 ms 324 KB Output is correct
24 Correct 1048 ms 324 KB Output is correct
25 Correct 794 ms 296 KB Output is correct
26 Correct 1040 ms 304 KB Output is correct
27 Execution timed out 2088 ms 5700 KB Time limit exceeded
28 Halted 0 ms 0 KB -