Submission #1123195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123195		dosts	Hacker (BOI15_hac)	C++20	100 / 100	58 ms	16468 KiB

hac

//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 2e18,MOD = 998244353,N = 2e5+1;

int add(int x,int y){
    return ((x+y) >= MOD ? x+y-MOD : x+y);
}

int mult(int x,int y) {
    return ((x*y)%MOD);
}

struct Q {
    stack<pii> s1,s2;

    void push(int op) {
        if (!s1.empty()) s1.push({op,min(s1.top().ss,op)});
        else s1.push({op,op});
    }

    void pop() {
        if (s2.empty()) {
            int cur = inf;
            while (!s1.empty()) {
                cur = min(s1.top().ff,cur);
                s2.push({s1.top().ff,cur});
                s1.pop();
            }
        }
        s2.pop();
    }
    int mn() {
        int pp;
        if (!s1.empty() && !s2.empty()) pp = min(s2.top().ss,s1.top().ss);
        else if (!s1.empty()) pp = s1.top().ss;
        else if (!s2.empty()) pp = s2.top().ss;
        else pp = inf;
        return pp;
    }
};

void solve() {
    int n;
    cin >> n;
    int ans = 0;
    vi a(n+1),p(n+1,0);
    for (int i=1;i<=n;i++) cin >> a[i]; 
    for (int i=1;i<=n;i++) p[i] = p[i-1]+a[i];
    //i...i-t+1 sliding min
    auto ask = [&](int l,int r) -> int {
        if (l <= r) return p[r]-p[l-1];
        return p[n]-p[l-1]+p[r];
    };
    vi f(n+1,0);
    int t = (n+1)/2;
    for (int i=1;i<=n;i++) {
        f[i] = ask(i,((i+t-1) > n ? (i+t-1)-n : (i+t-1)));
    }
    Q queue;
    for (int i=1;i<=t;i++) queue.push(f[i]);
    for (int i=t;i<=n+t-1;i++) {
        /* cout << i sp queue.mn() << '\n'; */
        ans = max(ans,queue.mn());
        queue.pop();
        queue.push(f[i%n+1]);
    }
    cout << ans << '\n';
}                    
                             
int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);/* 
    #else 
      freopen("fcolor.in","r",stdin);
      freopen("fcolor.out","w",stdout); */
    #endif
    
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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