Source Code
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mp make_pair
#define pb push_back
#define lp(i,s,f) for(ll i = s; i < ll(f); i++)
#define inF freopen("input.in", "r", stdin);
#define outF freopen("output.in", "w", stdout);
#define endl '\n'
#define MOD 1000000007
#define mm(arr) memset(arr, 0, sizeof(arr))
#define F first
#define S second
#define int ll

const long double PI = atan(1) * 4.0;

const int N = 2e6 + 1;
bool prime[N];
vector<int> primes;
int mx[N];
void sieve(){
    for(int i = 1; i < N; i++){
        prime[i] = 1;
    }
    mx[0] = 0;
    mx[1] = 1;
    mx[2] = 2;
    primes.pb(2);
    prime[1] = 0;
    prime[0] = 0;
    for(int i = 4; i < N; i+=2){
        prime[i] = 0;
        mx[i] = 2;
    }
    for(int i = 3; i < N; i++){
        if(prime[i]){
            mx[i] = i;
            primes.pb(i);
            for(int j = i + i; j < N; j += i){
                prime[j] = 0;
                mx[j] = i;
            }
        }
    }
}

int get_bits(int num){
    int cnt = 0;
    while(num != 0){
        num /= 2;
        cnt++;
    }
    return cnt;
}

int32_t main(){
    FAST
    sieve();
    int n; cin >> n;
    int old_n = n;
    vector<int> vec(n, 0);
    for(int i = 0; i < n; i++){
        cin >> vec[i];
    }
    vec.pb(0);
    n = vec.size();
    vector<int> new_vec = vec;
    for(int i = 0; i < n - 1; i++){
        new_vec[i] = max(vec[i], vec[i + 1]);
    }
    swap(vec, new_vec);
    n = vec.size();
    while(vec.size()%2 == 1){
        n = vec.size();
        int sum = 0;
        for(int j = n - 1; j >= 0 && sum + vec[j] <= old_n; j--){
            sum += vec.back();
            vec.pop_back();
        }
    }
    n = vec.size();
    vector<int> v1, v2;
    for(int i = 0; i < n/2; i++){
        v1.pb(vec[i]);
    }
    for(int i = n/2; i < n; i++){
        v2.pb(vec[i]);
    }
    reverse(v1.begin(), v1.end());
    reverse(v2.begin(), v2.end());
    for(int i = 0; i < n/2; i++){
        vec[i] = v1[i];
    }
    for(int i = n/2; i < n; i++){
        vec[i] = v2[i - n/2];
    }
    vec.pb(3);
    vec.pb(2);
    vec.pb(1);
    n = vec.size();
    for(int i = 0; i < n; i++){
        if(vec[i] > vec[n - 1]){
            swap(vec[i], vec[n - 1]);
        }
    }
    vec[0] = 1031;
    for(int i = 0; i < n; i++){
        vec[i] = mx[vec[i]];
    }
    sort(vec.rbegin(), vec.rend());
    for(int i = 0; i < n; i++){
        vec[i] %= 16384;
    }
    for(int i = 1; i + 2 < n; i++){
        if(vec[i] == 6 && vec[i + 1] == 7 && vec[i + 2] == 9){
            swap(vec[i], vec[i - 1]);
        }
    }
    for(int i = 0; i < n; i++){
        vec[i] *= __builtin_popcountll(vec[i]);
    }
    vec.pb(3);
    vec.pb(2);
    vec.pb(1);
    n = vec.size();
    for(int i = 0; i < n; i++){
        if(vec[i] > vec[n - 1]){
            swap(vec[i], vec[n - 1]);
        }
    }
    vec[0] = 1031;
    for(int i = 0; i < n; i++){
        vec[i] = mx[vec[i]];
    }
    sort(vec.rbegin(), vec.rend());
    for(int i = 0; i < n; i++){
        vec[i] %= 16384;
    }
    for(int i = 1; i + 2 < n; i++){
        if(vec[i] == 6 && vec[i + 1] == 7 && vec[i + 2] == 9){
            swap(vec[i], vec[i - 1]);
        }
    }
    for(int i = 0; i < n; i++){
        vec[i] *= __builtin_popcountll(vec[i]);
    }
    if(vec[0] == 0 || vec.back() == 0){
        vec = {1, 2, 3, 4, 5};
    }
    n = vec.size();
    int sum = 0;
    for(int i = 0; i < n; i++){
        sum += vec[i] * (i + 1);
    }
    cout << sum;
    return 0;
}
Copy
Slavery Basilhijaz
GNU G++17
161 ms
23.5 MB
Accepted