Submission #340191

#TimeUsernameProblemLanguageResultExecution timeMemory
340191blueHacker (BOI15_hac)C++11
100 / 100
546 ms18476 KiB
#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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...