Submission #1192623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192623		sunboi	Hacker (BOI15_hac)	C++20	100 / 100	492 ms	23960 KiB

hac

#include <bits/stdc++.h>
using namespace std;
#define int long long



signed main() {
    int n; cin >> n;
    vector<int> a(n), pref(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
        pref[i] = a[i];
        if (i > 0) pref[i] += pref[i - 1];
    }
    
    map<int, int> valores;
    int ans = 0;
    int x = (n - 1) / 2;
    for (int i = -x; i <= 0; i++){
        
        if (i == 0) valores[pref[x + i]]++;
        else{
            valores[pref[x + i] + pref[n - 1] - pref[n - 1 + i]]++;
        }
        
        
    }
    
    /*for (auto [key, val] : valores){
        cout << key << ' ' << val << endl;
    }
    cout << endl;*/
    
    ans = valores.begin()->first;
    
    for (int i = 1; i < n; i++){
        int cantidad = pref[i - 1];
        
        if (i - x - 1 >= 0) {
            if (i - x - 2 >= 0) cantidad -= pref[i - x - 2];
        }
        else cantidad += pref[n - 1] - pref[n - 1 + i - x - 1];
        

        valores[cantidad]--;
        if (valores[cantidad] == 0) valores.erase(cantidad);
        
        
        
        if (i + x >= n) cantidad = cantidad = pref[n - 1] - pref[i - 1] + pref[i + x - n];
        else cantidad = pref[i + x] - pref[i - 1];
        
        valores[cantidad]++;
        
        ans = max(ans, valores.begin()->first);
        
        /*for (auto [key, val] : valores){
            cout << key << ' ' << val << endl;
        }
        cout << endl;*/
    }
    
    cout << ans << endl;
    
    
}

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