oj.uz

Submission #823264

# Submission time Handle Problem Language Result Execution time Memory
823264 2023-08-12T10:12:11 Z serifefedartar Hacker (BOI15_hac) C++17
20 / 100
 148 ms 10500 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000009
#define LOGN 20
#define MAXN 500005


int n;
int sg[4*MAXN];
vector<int> v, pref;
int get_sum(int begin, int len) {
    if (begin + len - 1 <= n)
        return pref[begin + len - 1] - pref[begin - 1];
    else
        return pref[n] - pref[begin - 1] + pref[len - n + begin - 1];
}

void init(int k, int a, int b) {
    if (a == b) {
        sg[k] = get_sum(a, n/2);
        return ; 
    }
    init(2*k, a, (a+b)/2);
    init(2*k+1, (a+b)/2+1, b);
    sg[k] = max(sg[2*k], sg[2*k+1]);
}

int query(int k, int a, int b, int q_l, int q_r) {
    if (a > q_r || b < q_l)
        return 0;
    if (q_l <= a && b <= q_r)
        return sg[k];
    return max(query(2*k, a, (a+b)/2, q_l, q_r), query(2*k+1, (a+b)/2+1, b, q_l, q_r));
}

int main() {
    fast
    cin >> n;

    v = vector<int>(n+1);
    pref = vector<int>(n+1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        pref[i] = pref[i-1] + v[i]; 
    }
    init(1, 1, n);

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int max_protect;
        if (i + 1 + n/2 <= n)
            max_protect = query(1, 1, n, i + 1, i + n/2);
        else
            max_protect = max(query(1, 1, n, i + 1, n), query(1, 1, n, 1, i + n/2 - n));
        ans = max(ans, pref[n] - max_protect);
    }
    cout << ans << "\n";
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 23 ms 2344 KB Output is correct
5 Correct 55 ms 4692 KB Output is correct
6 Correct 74 ms 5428 KB Output is correct
7 Correct 84 ms 8028 KB Output is correct
8 Correct 148 ms 10500 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -