제출 #1119851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1119851		PagodePaiva	Hacker (BOI15_hac)	C++17	100 / 100	169 ms	43188 KiB

hac

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 500010;
const int LOGN = 20;
int pref[2*N];
int n;
int v[2*N];
int val[2*N];

struct Segtree{
    int tree[8*N];
    int join(int a, int b){
        return max(a, b);
    }
    void build(int node, int l, int r){
        if(l == r){
            tree[node] = val[l];
            return;
        }
        int mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1, mid+1, r);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    int query(int node, int l, int r, int tl, int tr){
        if(l > tr or tl > r) return 0;
        if(l <= tl and tr <= r) return tree[node];
        int mid =(tl+tr)/2;
        return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
    }
} seg;

int query(int l, int r){
    if(l > r) r += n;
    return pref[r]-pref[l-1];
}

int32_t main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> v[i];
        v[n+i] = v[i];
    }
    for(int i = 1;i <= 2*n;i++){
        pref[i] = pref[i-1]+v[i];
    }
    //int res = 0;
    int d = n/2;
    int sum = 0;
    for(int i = 1;i <= d;i++){
        sum += v[i];
    }
    for(int i = 1;i+d-1 <= 2*n;i++){
        val[i] = sum;
        if(i+d > 2*n) break;
        sum -= v[i];
        sum += v[i+d];
    }
    seg.build(1, 1, 2*n);
    int res = 0;
    for(int i = 1;i <= n;i++){
        int l = i, r = i+n;
        int tot = pref[r]-pref[l]-seg.query(1, l+1,r-d, 1, 2*n);
        res = max(res, tot);
    }
    cout << res  << '\n';
}

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