Submission #1111156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111156		Ghulam_Junaid	Hacker (BOI15_hac)	C++17	100 / 100	348 ms	18504 KiB

hac

#include <bits/stdc++.h>
using namespace std;
 
const int N = 5e5 + 10;
int n, a[N], x[N];
 
int norm(int x){
    x %= n;
    x += n;
    x %= n;
    return x;
}
 
int main(){
    cin >> n;
    for (int i = 0; i < n; i ++)
        cin >> a[i];
 
    int k = n / 2 + n % 2;
    for (int i = 0; i < k; i ++)
        x[0] += a[i];
 
    for (int i = 1; i < n; i ++)
        x[i] = x[i - 1] - a[i - 1] + a[(i + k - 1) % n];
 
    set<pair<int, int>> st;
    for (int i = 0; i < k; i ++)
        st.insert({x[i], i});
 
    int ans = 0;
    for (int i = k - 1; i < n + k - 1; i ++){
        ans = max(ans, (*st.begin()).first);
        st.erase({x[norm(i - k + 1)], norm(i - k + 1)});
        st.insert({x[norm(i + 1)], norm(i + 1)});
    }
 
    cout << ans << endl;
}

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