Submission #720144

#	Time	Username	Problem	Language	Result	Execution time	Memory
720144		Trent	Hacker (BOI15_hac)	C++17	100 / 100	135 ms	15612 KiB

hac

#include "bits/stdc++.h"
 
using namespace std;
#define forR(i, a) for(int i = 0; (i) < (a); ++(i))
#define REP(i, a, b) for(int i = (a); (i) < (b); ++i)
#define all(a) a.begin(), a.end()
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define printArr(arr) for(int asdfg : arr) cout << asdfg << ' '; cout << '\n'
#define open(x) freopen(((string) x + ".in").c_str(), "r", stdin); freopen(((string) x + ".out").c_str(), "w", stdout);
typedef long long ll;
struct pii{int a, b;};

const int MN = 2e6 + 10;
int v[MN], ra[MN];

signed main(){
    int n; cin >> n;
    int su = 0;
    forR(i, n) {
        cin >> v[i];
        su += v[i];
    }
    forR(i, n) v[i + n] = v[i + 2 * n] = v[i];
    int oSiz = n / 2;
    for(int i=0, oWin=0; i < 3 * n; ++i){
        oWin += v[i] - (i >= oSiz ? v[i-oSiz] : 0);
        if(i >= oSiz - 1) ra[i - oSiz + 1] = oWin;
    }
    deque<pii> ma;
    REP(i, 1, n-oSiz) {
        while(!ma.empty() && ma.back().b < ra[i]) ma.pop_back();
        ma.push_back({i, ra[i]});
    }
    int bes = 0;
    forR(i, n){
        int nex = i + n - oSiz;
        while(!ma.empty() && ma.back().b < ra[nex]) ma.pop_back();
        ma.push_back({nex, ra[nex]});
        if(i >= ma.front().a) ma.pop_front();
        bes = max(bes, su - ma.front().b);
    }
    cout << bes << '\n';
}

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