Submission #1171428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171428		InvMOD	Hacker (BOI15_hac)	C++20	100 / 100	144 ms	19784 KiB

hac

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

struct SMT{
    int trsz;
    vector<ll> st;

    SMT(int n = 0): trsz(n), st((n << 2 | 1), 1e15) {}

    void update(int id, int l, int r, int u, int v, ll val){
        if(l >= u && r <= v){
            st[id] = min(st[id], val);
            return;
        }
        int m = l+r>>1;

        st[id << 1] = min(st[id << 1], st[id]);
        st[id << 1|1] = min(st[id << 1|1], st[id]);

        if(u <= m) update(id << 1, l, m, u, v, val);
        if(v > m) update(id << 1|1, m+1, r, u, v, val);
    }

    ll query(int id, int l, int r, int x){
        if(l == r){
            return st[id];
        }
        int m = l+r>>1;

        st[id << 1] = min(st[id << 1], st[id]);
        st[id << 1|1] = min(st[id << 1|1], st[id]);

        if(x <= m)
            return query(id << 1, l, m, x);
        return query(id << 1|1, m+1, r, x);
    }

    void update(int l, int r, ll val){
        update(1, 1, trsz, l, r, val);
    }

    ll query(int x){
        return query(1, 1, trsz, x);
    }
};

void solve()
{
    int n; cin >> n;

    vector<ll> a(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] += a[i - 1];
    }


    SMT st(n); int len = (n >> 1) + (n & 1);
    for(int i = 1; i <= n; i++){
        int r = i + len - 1;

        ll total = a[min(r, n)] - a[i - 1];
        if(r > n){
            total = total + a[r - n];
        }

        st.update(i, min(r, n), total);
        if(r > n){
            st.update(1, r - n, total);
        }
    }

    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(ans, st.query(i));
    }

    cout << ans << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message (stderr)

hac.cpp: In function 'int32_t main()':
hac.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hac.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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