Submission #340191

#	Time	Username	Problem	Language	Result	Execution time	Memory
340191		blue	Hacker (BOI15_hac)	C++11	100 / 100	546 ms	18476 KiB

hac

#include <iostream>
#include <set>
using namespace std;

/*
For any starting position, the operator can force the hacker into any contiguous ceil(n/2) positions
containing that particular position.
*/

int main()
{
    int n;
    cin >> n;

    int v[n];
    int i, j;
    for(i = 0; i < n; i++) cin >> v[i];


    int a_size = n - (n/2);

    int w[n];
    w[0] = 0;
    for(j = 0; j < a_size; j++) w[0] += v[j];
    j--;
    for(i = 1; i < n; i++)
    {
        w[i] = w[i-1] + v[(i + a_size - 1) % n] - v[i-1];
    }

    multiset<int> S;
    for(j = 0; j < a_size; j++) S.insert(w[j]);
    j--;
    int res = *S.begin();
    for(i = 1; i < n; i++)
    {
        S.insert(w[(i + a_size - 1) % n]);
        S.erase(S.find(w[i-1]));
        res = max(res, *S.begin());
    }
    cout << res << '\n';
}

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