Test results - Codility

Tasks Details

medium

1. StacksOfCoins

Move coins between the given stacks to obtain a stack with the maximum possible number of coins.

Task Score

100%

Correctness

100%

Performance

100%

There are N stacks of coins, numbered from 0 to N−1. The Kth stack has A[K] coins. In one move we can pick two coins from any stack we choose, put the first coin away and place the second coin on the adjacent stack (either to the left or to the right of the original stack).

What is the maximum number of coins that can be accumulated in a single stack?

Write a function:

int solution(vector<int> &A);

that, given an array A of N integers, recording the heights of the stacks, returns the maximum number of coins that can be accumulated in one stack after performing any number of moves as described above.

Examples:

1. Given A = [2, 3, 1, 3], the function should return 5. A possible sequence of moves is: [2, 3, 1, 3] → [0, 4, 1, 3] → [0, 4, 2, 1] → [0, 5, 0, 1].

2. Given A = [3, 7, 0, 5], the function should return 9. A possible sequence of moves is: [3, 7, 0, 5] → [1, 8, 0, 5] → [1, 8, 1, 3] → [1, 8, 2, 1] → [1, 9, 0, 1].

3. Given A = [1, 1, 1, 1, 1], the function should return 1. No move can be performed.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..200,000];

each element of array A is an integer within the range [0..100,000,000].

Solution

Programming language used C++

Time spent on task 8 minutes

Notes

not defined yet

Code: 17:00:27 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
    }
}

Code: 17:00:27 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
    }
}

Code: 17:00:37 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
}

Code: 17:03:13 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(vector<int> &a) {
    // write your code in C++14 (g++ 6.2.0)
}

Code: 17:03:32 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<int> pref(n+1)
}

Code: 17:04:02 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<int> pref(n), suff(n);
    pref[0] = a[0];
    
}

Code: 17:04:24 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<int> pref(n), suff(n);
    pref[0] = a[0];
    FORI(i,1,n){
        pref[i] = a[i] + pref[i-1] / 2;
    }
}

Code: 17:04:45 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<int> pref(n), suff(n);
    pref[0] = a[0];
    FORI(i,1,n){
        pref[i] = a[i] + pref[i-1] / 2;
    }
    suff[n-1] = a[n-1];
    FORD(i,n-1,-1){
        pref[i] = a[i] + pref[i-1] / 2;
    }
}

Code: 17:04:56 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<int> pref(n), suff(n);
    pref[0] = a[0];
    FORI(i,1,n){
        pref[i] = a[i] + pref[i-1] / 2;
    }
    suff[n-1] = a[n-1];
    FORD(i,n-1,0){
        suff[i-1] = a[i] + pref[i-1] / 2;
    }
}

Code: 17:05:08 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<int> pref(n), suff(n);
    pref[0] = a[0];
    FORI(i,1,n){
        pref[i] = a[i] + pref[i-1] / 2;
    }
    suff[n-1] = a[n-1];
    FORD(i,n-1,0){
        suff[i-1] = a[i-1] + suff[i] / 2;
    }
}

Code: 17:05:22 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<int> pref(n), suff(n);
    pref[0] = a[0];
    FORI(i,1,n){
        pref[i] = a[i] + pref[i-1] / 2;
    }
    suff[n-1] = a[n-1];
    FORD(i,n-1,0){
        suff[i-1] = a[i-1] + suff[i] / 2;
    }
    FORI(i,0,n){
        
    }
}

Code: 17:05:36 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<int> pref(n+1, 0), suff(n+1, 0);
    pref[0] = a[0];
    FORI(i,1,n){
        pref[i] = a[i] + pref[i-1] / 2;
    }
    suff[n-1] = a[n-1];
    FORD(i,n-1,0){
        suff[i-1] = a[i-1] + suff[i] / 2;
    }
    FORI(i,0,n){

    }
}

Code: 17:05:57 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<int> pref(n+1, 0), suff(n+1, 0);
    pref[0] = a[0];
    FORI(i,1,n){
        pref[i] = a[i] + pref[i-1] / 2;
    }
    suff[n-1] = a[n-1];
    FORD(i,n-1,0){
        suff[i-1] = a[i-1] + suff[i] / 2;
    }
    FORI(i,0,n){
        
    }
}

Code: 17:06:08 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<int> pref(n+1, 0), suff(n+1, 0);
    FORI(i,1,n+1){
        pref[i] = a[i] + pref[i-1] / 2;
    }
    suff[n-1] = a[n-1];
    FORD(i,n-1,0){
        suff[i-1] = a[i-1] + suff[i] / 2;
    }
    FORI(i,0,n){
        
    }
}

Code: 17:06:19 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<int> pref(n+1, 0), suff(n+1, 0);
    FORI(i,1,n+1){
        pref[i] = a[i-1] + pref[i-1] / 2;
    }
    FORD(i,n,0){
        suff[i-1] = a[i-1] + suff[i] / 2;
    }
    FORI(i,0,n){
        
    }
}

Code: 17:06:49 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<LL> pref(n+1, 0), suff(n+1, 0);
    FORI(i,1,n+1){
        pref[i] = a[i-1] + pref[i-1] / 2;
    }
    FORD(i,n,0){
        suff[i-1] = a[i-1] + suff[i] / 2;
    }
    LL ans = 0;
    FORI(i,0,n){
        ans
    }
}

Code: 17:07:01 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<LL> pref(n+1, 0), suff(n+1, 0);
    FORI(i,1,n+1){
        pref[i] = a[i-1] + pref[i-1] / 2;
    }
    FORD(i,n,0){
        suff[i-1] = a[i-1] + suff[i] / 2;
    }
    LL ans = 0;
    FORI(i,0,n+1){
        ans = max(ans, pref[i])
    }
}

Code: 17:07:12 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<LL> pref(n+1, 0), suff(n+1, 0);
    FORI(i,1,n+1){
        pref[i] = a[i-1] + pref[i-1] / 2;
    }
    FORD(i,n,0){
        suff[i-1] = a[i-1] + suff[i] / 2;
    }
    LL ans = 0;
    FORI(i,0,n){
        ans = max(ans, pref[i] + a[i] + suff[i+1])
    }
}

Code: 17:07:42 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<LL> pref(n+1, 0), suff(n+1, 0);
    FORI(i,1,n+1){
        pref[i] = a[i-1] + pref[i-1] / 2;
    }
    FORD(i,n,0){
        suff[i-1] = a[i-1] + suff[i] / 2;
    }
    LL ans = 0;
    FORI(i,0,n){
        ans = max(ans, pref[i] / 2 + a[i] + suff[i+1] / 2);
    }
    return ans
}

Code: 17:07:43 UTC, cpp, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<LL> pref(n+1, 0), suff(n+1, 0);
    FORI(i,1,n+1){
        pref[i] = a[i-1] + pref[i-1] / 2;
    }
    FORD(i,n,0){
        suff[i-1] = a[i-1] + suff[i] / 2;
    }
    LL ans = 0;
    FORI(i,0,n){
        ans = max(ans, pref[i] / 2 + a[i] + suff[i+1] / 2);
    }
    return ans;
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.001 s

▶

example2
Second example test.

✔

0.001 s

▶

example3
Third example test.

✔

0.001 s

Code: 17:08:05 UTC, cpp, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<LL> pref(n+1, 0), suff(n+1, 0);
    FORI(i,1,n+1){
        pref[i] = a[i-1] + pref[i-1] / 2;
    }
    FORD(i,n,0){
        suff[i-1] = a[i-1] + suff[i] / 2;
    }
    LL ans = 0;
    FORI(i,0,n){
        ans = max(ans, pref[i] / 2 + a[i] + suff[i+1] / 2);
    }
    return ans;
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.001 s

▶

example2
Second example test.

✔

0.001 s

▶

example3
Third example test.

✔

0.001 s

Code: 17:08:11 UTC, cpp, final, score: 100

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7;

int solution(V<int> &a) {
    int n = a.size();
    V<LL> pref(n+1, 0), suff(n+1, 0);
    FORI(i,1,n+1){
        pref[i] = a[i-1] + pref[i-1] / 2;
    }
    FORD(i,n,0){
        suff[i-1] = a[i-1] + suff[i] / 2;
    }
    LL ans = 0;
    FORI(i,0,n){
        ans = max(ans, pref[i] / 2 + a[i] + suff[i+1] / 2);
    }
    return ans;
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

expand all Example tests

▶

example1
First example test.

✔

0.001 s

▶

example2
Second example test.

✔

0.001 s

▶

example3
Third example test.

✔

0.001 s

expand all Correctness tests

▶

small
N <= 5.

✔

0.001 s

▶

equal_small
All numbers are the same. N = 100.

✔

0.001 s

▶

random_small
Heights of stacks are randomly generated. N = 100.

✔

0.001 s

▶

sorted_medium
Stacks are sorted by height (decreasingly or increasingly). N = 1,000.

✔

0.001 s

▶

random_medium
Heights of stacks are randomly generated. N = 1,000.

✔

0.001 s

expand all Performance tests

▶

almost_equal_large
Stacks have similar heights (differ by at most 10).

✔

0.012 s

0.024 s

0.012 s

▶

sorted_large
Stacks are sorted by height (decreasingly or increasingly).

✔

0.024 s

0.016 s

▶

random_large
Heights of stacks are randomly generated.

✔

0.024 s