Submission #1127425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127425		andrewp	Hacker (BOI15_hac)	C++20	100 / 100	351 ms	21972 KiB

hac

//Dedicated to my love,ivaziva 
#include <bits/stdc++.h>  
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long 
#define sz(a) ((int) (a).size())
#define pb emplace_back 
#define me(a, x) memset(a, x, sizeof(a)) 
#define vi vector<int> 
#define i128 __int128
using namespace std;    
const int N = 1e6 + 7; 
int n, a[N], ps[N], ans[N]; 
int main() { 
    ios :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
     
    cin >> n;
    int sum = 0;
    L(i, 1, n) {
        cin >> a[i];
        a[i + n] = a[i];
        ans[i] = (int)(1e9 + 1);
    }
    L(i, 1, 2 * n) ps[i] = ps[i - 1] + a[i]; 
    int len = (n + 1) / 2, sol = 0;
    multiset<int> ms;
    L(i, 1, 2 * n) {
        if(i + len <= 2 * n + 1) ms.insert(ps[i + len - 1] - ps[i - 1]);
        if(i > len) ms.erase(ms.find(ps[i - 1] - ps[i - len - 1]));
        int ei = i;
        if(ei > n) ei -= n;
        ans[ei] = min(ans[ei], *ms.begin());
    }
    L(i, 1, n) sol = max(sol, ans[i]);
    cout << sol << '\n';
    return 0;
} 

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