Submission #426923

#	Time	Username	Problem	Language	Result	Execution time	Memory
426923		fvogel499	Hacker (BOI15_hac)	C++14	100 / 100	308 ms	12884 KiB

hac

/*
File created on 06/14/2021 at 12:41:02.
Link to problem: 
Description: 
Time complexity: O()
Space complexity: O()
Status: DEV
Copyright: Ⓒ 2021 Francois Vogel
*/

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second

#define pb push_back
#define ins insert
#define cls clear

#define ll long long

const int p2 = 1<<20;
const int inf = 1e9;
int bt [p2*2];
void btCls() { for (int i = 0; i < p2*2; i++) bt[i] = inf; }
void btUpd(int rb, int re, int rv, int qn = 1, int qb = 0, int qe = p2-1) {
    if (rb > qe or qb > re) return;
    else if (rb <= qb and qe <= re) bt[qn] = min(bt[qn], rv);
    else {
        int qm = (qb+qe)/2;
        btUpd(rb, re, rv, qn*2, qb, qm);
        btUpd(rb, re, rv, qn*2+1, qm+1, qe);
    }
}
int btGet(int idx) {
    int mnv = inf;
    for (idx += p2; idx != 0; idx /= 2) mnv = min(mnv, bt[idx]);
    return mnv;
}

signed main() {
    cin.tie(0);
    // ios_base::sync_with_stdio(0);

    int n;
    cin >> n;
    int b [n];
    for (int i = 0; i < n; i++) cin >> b[i];
    btCls();
    int divS = (n+1)/2;
    int curSum = 0;
    for (int i = 0; i < divS; i++) curSum += b[i];
    for (int i = 0; i < n; i++) {
        int start = i;
        int end = (i+divS-1)%n;
        if (start < end) {
            btUpd(start, end, curSum);
        }
        else {
            btUpd(start, n-1, curSum);
            btUpd(0, end, curSum);
        }
        curSum -= b[i];
        curSum += b[(i+divS)%n];
    }
    int mxv = 0;
    for (int i = 0; i < n; i++) {
        mxv = max(mxv, btGet(i));
    }
    cout << mxv;

    int d = 0;
    d++;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40