Submission #639923

#	Time	Username	Problem	Language	Result	Execution time	Memory
639923		Wunka	Hacker (BOI15_hac)	C++17	100 / 100	325 ms	26244 KiB

hac

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long 
 
struct segtree {
    vector<ll> tree; 
    int size = 1; 
 
    void init(int n) {
        while(size < n) size *= 2; 
        tree.assign(2 * size - 1, 0);
    }
 
    void set(int i, ll v, int x, int lx, int rx) {
        if(rx - lx == 1) {
            tree[x] = v;
            return; 
        } 
        
        int mid = (lx + rx) / 2; 
        if(i < mid) {
            set(i, v, 2 * x + 1, lx, mid); 
        }
        else{
            set(i, v, 2 * x + 2, mid, rx); 
        }
        tree[x] = max(tree[2 * x + 1], tree[2 * x + 2]); 
    }
    void set(int i, ll v) {
        set(i, v, 0, 0, size); 
    }
 
 
    ll get_max(int l, int r, int x, int lx, int rx) {
        if(lx >= r || rx <= l) return 0; 
        if(lx >= l && rx <= r) return tree[x]; 
        int mid = (lx + rx) / 2; 
 
        ll m1 = get_max(l, r, 2 * x + 1, lx, mid);
        ll m2 = get_max(l, r, 2 * x + 2, mid, rx); 
        return max(m1, m2);  
    }
    ll get_max(int l, int r) {
        return get_max(l, r, 0, 0, size); 
    }
}; 
 
// NOTE: Pentru al doilea jucator marimea lantului o sa fie floor(n / 2), de aceea o sa fac i + (n / 2)
 
vector<ll> computeNsums(vector<ll>& a) {
    int n = a.size() / 2;
    vector<ll> nsums(n); 
    vector<ll> pref(2 * n + 1);
    for(int i = 0; i < 2 * n; i++) {
        pref[i + 1] = pref[i] + a[i]; 
    }
 
    for(int i = 0; i < n; i++) {
        nsums[i] = pref[i + (n / 2)] - pref[i]; 
    }
 
    return nsums;
}
 
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
 
    int n; 
    cin >> n; 
    vector<ll> a(2 * n); 
    ll S = 0; 
    for(int i = 0; i < n; i++) {
        cin >> a[i]; 
        a[i + n] = a[i]; 
        S += a[i]; 
    }
    
    vector<ll> b = computeNsums(a); 
    //cout << "our b array: "; 
    //for(int i = 0; i < n; i++) cout << b[i] << ' '; 
    //cout << '\n'; 
    /*
    segtree st; 
    st.init(n); 
    for(int i = 0; i < n; i++) {
        st.set(i, b[i]); 
    }
    //cout << "THIS IS OUR SUM:" << S << '\n'; 
    //cout << '\n'; 
    ll ans = 0; 
    for(int i = 0; i < n; i++) {
        cout << "we are in position " << i << '\n'; 
        int l = (i + 1) % n, r = ((i - (n + 1) / 2) + n) % n; 
        int mn = min(l, r), mx = max(l, r); 
        cout << "currently our admissible interval:" << mn << ' ' << mx << '\n'; 
        //ll res = st.get_max(mn, mx + 1); 
        //ans = max(ans, S - st.get_max(mn, mx + 1)); 
        //cout << '\n'; 
        ll m1 = st.get_max(0, mn + 1), m2 = st.get_max((i + 1) % n, mx + 1); 
        ll res = max(m1, m2); 
        ans = max(ans, S - res); 
        cout << "comparing " << ans << " with " << res << " which is "<< S - res << '\n';
        cout << '\n'; 
    }
    
    // (L; R) - de la care element putem sa formam sirul, cu care element se incepe ultimul sir. 
    for(int i = 0; i < n; i++) {
        int L = (i + 1) % n, R = ((i - (n + 1) / 2) + n) % n; 
        // L should be greater than R
        if(R > L) {
            swap(R, L); 
        }
        ll m1 = st.get_max(L, n + 1), m2 = st.get_max(0, R + 1); 
        ll res = max(m1, m2); 
        ans = max(ans, S - res);
 
    }
    */ 
    // este o modalitate cum se poate de rezolvat problema fara de segment tree : observam ca noi ca si cum miscam un interval de marimea k si in el noi scoatem cel mai din stanga elemente si adaugam cel mai din dreapta element, atunci cand miscam intervalul dat. aceasta ne da ideea de sliding window.  
    ll ans = 0; 
    ll L = 1, R = n - (n / 2);  
    multiset<ll> window; 
    for(int i = L; i <= R; i++){
        window.insert(-b[i]); 
    } 
 	// fucking constant factor si trebuie de transformat in negative 
    for(int i = 0; i < n; i++) {
        ll res = -(*window.begin()); 
        ans = max(ans, S - res); 
        window.erase(window.find(-b[L])); 
        L = (L + 1) % n; 
        R = (R + 1) % n; 
        window.insert(-b[R]); 
    }
    //cout << "========================================" << '\n'; 
    cout << ans << '\n'; 
}
 
/*
    Diferenta intre v1 si v2. 
    -- Daca ambii jucaturi incearca sa imi maximizeze scorul sau, aceasta nu inseamna faptul ca raspunsul o sa fie obligatoriu ca primul o sa aiba mai mare valoarea decat al doilea jucator SAU ca in asemenea situatie cand diferenta intre scoruri o sa fie minimala --> noi o sa avem cel mai mare raspuns pentru X. MOtivul pentru aceasta consta intr-aceea, ca asemenea ipoteze nu obligatoriu asuma ca al doilea jucator are strategie optimala, de aceea nu putem sa spunem ca ele sunt corecte. 
 
 
    Observam ca dupa prima miscare noi deja stim cum o sa arate primul sir si noi stim cum o sa arata sirul la al doilea jucator. De ce?
    Pentru ca sirul primului jucator este format unic - obligatoriu o sa se invarte intre intervalele de marimea k, care contin primul varf ales, al doilea jucator o sa incearca sa faca asa un pas - astfel incat valoarea sirului primului jucator, o sa fie minimal posibila. Cum procedeaza al doilea jucator? Noi precomputam pentru fiecare varf X, care este valoarea sirului care porneste din X si are marimea k, daca sirul merge in ordinea acelor ceasornicului. 
 
    Dupa aceasta, noi incercam din toate sirurile acestea, care nu il contin pe X - sa luam intervalul cu sma maximala. SUma_sirului1 = S - suma_sirului2. Problema s-a redus la cautarea banala valorii maximale a suma_sirului1. 
 
*/

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