oj.uz

Submission #137484

# Submission time Handle Problem Language Result Execution time Memory
137484 2019-07-28T03:28:23 Z silxikys Hacker (BOI15_hac) C++14
20 / 100
 74 ms 8144 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 5e5+5;
int n;
int v[2*maxn];
int pre[2*maxn];

struct MaxQueue
{
    deque<pair<ll,int>> q;
    int cnt_added = 0;
    int cnt_removed = 0;
    ll maximum() {
        assert(!q.empty());
        return q.front().first;
    }
    void push(ll new_element) { //add new element
        while (!q.empty() && q.back().first < new_element) {
            q.pop_back();
        }
        q.push_back({new_element,cnt_added});
        cnt_added++;
    }
    void pop() {
        if (!q.empty() && q.front().second == cnt_removed) {
            q.pop_front();
        }
        cnt_removed++;
    }
};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        v[i+n] = v[i];
    }
    pre[0] = v[0];
    for (int i = 1; i < 2*n; i++) {
        pre[i] = pre[i-1] + v[i];
    }
    int total = pre[n-1];
    MaxQueue mq;
    for (int i = n/2; i < n; i++) {
        mq.push(pre[i]-pre[i-n/2]);
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        int maxSum = mq.maximum();
        res = max(res,total-maxSum);
        mq.pop();
        mq.push(pre[i+1+n]-pre[i+1+n-n/2]);
    }
    cout << res << '\n';
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 12 ms 1656 KB Output is correct
5 Correct 28 ms 3448 KB Output is correct
6 Correct 40 ms 4344 KB Output is correct
7 Correct 45 ms 4988 KB Output is correct
8 Correct 74 ms 8144 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -