Submission #146130

#	Time	Username	Problem	Language	Result	Execution time	Memory
146130		evpipis	Hacker (BOI15_hac)	C++11	100 / 100	324 ms	8952 KiB

hac

#include <bits/stdc++.h>
using namespace std;

const int len = 5e5+5, inf = 1e9;
int arr[len], out[len], val[4*len], n;

void build(int p, int l, int r){
    val[p] = inf;

    if (l == r)
        return;

    int mid = (l+r)/2;
    build(2*p, l, mid);
    build(2*p+1, mid+1, r);
}

void prop(int p, int l, int r){
    if (val[p] == inf || l == r)
        return;

    val[2*p] = min(val[2*p], val[p]);
    val[2*p+1] = min(val[2*p+1], val[p]);
    val[p] = inf;
}

void upd(int p, int l, int r, int i, int j, int v){
    prop(p, l, r);
    if (r < i || j < l)
        return;
    if (i <= l && r <= j)
        return void(val[p] = min(val[p], v));

    int mid = (l+r)/2;
    upd(2*p, l, mid, i, j, v);
    upd(2*p+1, mid+1, r, i, j, v);
}

int ask(int p, int l, int r){
    prop(p, l, r);
    if (l == r)
        return val[p];

    int mid = (l+r)/2;
    return max(ask(2*p, l, mid), ask(2*p+1, mid+1, r));
}

void change(int i, int j, int v){
    if (i <= j){
        upd(1, 0, n-1, i, j, v);
    }
    else{
        upd(1, 0, n-1, i, n-1, v);
        upd(1, 0, n-1, 0, j, v);
    }
}

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    build(1, 0, n-1);

    int k = (n+1)/2;
    for (int i = 0, j = 0, sum = 0; i < n; i++){
        while ((n+j-i)%n < k){
            sum += arr[j];
            j = (j+1)%n;
        }

        change(i, (j+n-1)%n, sum);
        sum -= arr[i];
    }

    printf("%d\n", ask(1, 0, n-1));
    return 0;
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
hac.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~

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