Submission #104605

#	Time	Username	Problem	Language	Result	Execution time	Memory
104605		teomrn	Hacker (BOI15_hac)	C++14	100 / 100	142 ms	17736 KiB

hac

#include <iostream>
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;

struct MinHeap {
    priority_queue <int> added, removed;

    void add(int x) {
        added.push(-x);
    }
    void rem(int x) {
        removed.push(-x);
    }

    int top() {
        while (!removed.empty() && removed.top() == added.top())
            removed.pop(), added.pop();
        return -added.top();
    }

    MinHeap() {
        added.push(-2e9);
    }
} h;

const int NMAX = 500010;
int vals[NMAX];
int sp[2 * NMAX];
int ans[2 * NMAX];

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d", vals + i);
        sp[i] = sp[i + n] = vals[i];
    }

    for (int i = 1; i < 2 * n; i++)
        sp[i] += sp[i - 1];

    int l = (n + 1) / 2;
    fill(ans, ans + 2 * n, 2e9);

    for (int i = 0; i + l - 1 < 2 * n; i++) {
        int val = sp[i + l - 1] - (i ? sp[i - 1] : 0);
        h.add(val);
        ans[i] = h.top();

        if (i >= l - 1) {
            int val = sp[i] - (i >= l ? sp[i - l] : 0);
            h.rem(val);
        }
    }

    int best = 0;

    for (int i = 0; i < n; i++) {
        int act = min(ans[i], ans[i + n]);
        best = max(best, act);
    }

    printf("%d\n", best);

    return 0;
}

Compilation message (stderr)

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

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