Submission #104610

#	Time	Username	Problem	Language	Result	Execution time	Memory
104610		alexpetrescu	Hacker (BOI15_hac)	C++14	100 / 100	105 ms	7800 KiB

hac

#include <cstdio>
#include <algorithm>

//FILE *fin = fopen("a.in", "r"), *fout = fopen("a.out", "w");
#define fin stdin
#define fout stdout

#define MAXN 500009

int v[2 * MAXN], dq[MAXN], sum[MAXN];

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

    for (int i = 1; i <= n; i++)
        fscanf(fin, "%d", &v[i]);

    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + v[i];

    int l = n / 2;
    for (int i = 1; i < l; i++)
        v[i] = sum[i] + sum[n] - sum[n - l + i];
    for (int i = l; i <= n; i++)
        v[i] = sum[i] - sum[i - l];
    for (int i = n + 1; i <= 2 * n; i++)
        v[i] = v[i - n];

    int st = 0, dr = 0, ans = 0;
    for (int i = 1; i <= 2 * n; i++) {
        if (st < dr && i - dq[st] == n - l)
            st++;
        while (st < dr && v[i] >= v[dq[dr - 1]])
            dr--;
        dq[dr++] = i;
        if (i >= n - l)
            ans = std::max(ans, sum[n] - v[dq[st]]);
    }

    fprintf(fout, "%d\n", ans);

    fclose(fin);
    fclose(fout);
    return 0;
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:14:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fin, "%d", &n);
     ~~~~~~^~~~~~~~~~~~~~~
hac.cpp:17:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf(fin, "%d", &v[i]);
         ~~~~~~^~~~~~~~~~~~~~~~~~

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