Submission #94116

#	Time	Username	Problem	Language	Result	Execution time	Memory
94116		Kastanda	Hacker (BOI15_hac)	C++11	100 / 100	122 ms	18488 KiB

hac

#include<bits/stdc++.h>
using namespace std;
const int N = 1000006;
int n, A[N], P[N], G[N], MN[N * 2];
inline void Set(int i, int val)
{
    for (i += n + n - 1; i; i >>= 1)
        MN[i] = min(MN[i], val);
}
inline int Get(int l, int r)
{
    int Mn = INT_MAX;
    l += n + n - 1;
    r += n + n - 1;
    for (; l < r; l >>= 1, r >>= 1)
    {
        if (l & 1) Mn = min(Mn, MN[l]), l ++;
        if (r & 1) r --, Mn = min(Mn, MN[r]);
    }
    return (Mn);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &A[i]), A[i + n] = A[i];

    int len = (n + 1) >> 1;

    for (int i = n; i < n + len; i++)
        P[n] += A[i];
    for (int i = n - 1; i; i--)
        P[i] = P[i + 1] + A[i] - A[i + len];

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

    memset(MN, 63, sizeof(MN));
    for (int i = 1; i <= n + n; i++)
        Set(i, P[i]);

    int Mx = 0;
    for (int i = n + 1; i <= n + n; i++)
    {
        int le = (n - 2) >> 1;
        if (n & 1)
            le = (n - 2 + 1) >> 1;
        Mx = max(Mx, Get(i - le, i + 1));
    }
    return !printf("%d", Mx);
}

Compilation message (stderr)

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

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