Submission #1299301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299301		nmhung	Hacker (BOI15_hac)	C++20	100 / 100	47 ms	24856 KiB

hac

#include <bits/stdc++.h>

using namespace std;

#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define rf if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}

#define bit(i, mask) (((mask) >> (i)) & 1)
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define vi vector<int>
#define all(a) (a).begin(), (a).end()
#define len(x) ((int)(x).size())
#define pb push_back
#define endl '\n'

#define name "test"

template<typename T1, typename T2> bool mini(T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int mod = 1e9 + 7;
const int inf = 1e9 + 9;
const ll  oo  = 1e18l + 7;
const int M   = 5e5 + 6;
const int N   = 1e6 + 6;
const int LOG = 31 - __builtin_clz(N);

int n, a[N];
ll pre[N], sum[N], ans[N];

void inp(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
}

void proc(){
    for(int i = 1; i <= 2 * n; i++) pre[i] = pre[i - 1] + a[i + (i > n ? -n : 0)];
    int len = (n + 1) / 2;
    for(int i = 1; i <= 2 * n; i++){
        if(i <= n) sum[i] = pre[i + len - 1] - pre[i - 1];
        else sum[i] = sum[i - n];
    }

    deque<int> dq;
    for(int i = 1; i <= 2 * n; i++){
        while(!dq.empty() && dq.front() < i - len + 1) dq.pop_front();
        while(!dq.empty() && sum[dq.back()] >= sum[i]) dq.pop_back();
        dq.pb(i);

        if(i >= len) ans[i - len + 1] = sum[dq.front()];
    }
    ll res = 0;
    for(int i = 1; i <= n; i++) maxi(res, ans[i]);
    cout << res;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);

    rf

    int test = 1;
//    cin >> test;

    while(test--){
        inp();
        proc();
    }

    cerr << "Time elapsed: " << TIME << "s" << endl;
    return 0;
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:6:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define rf if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hac.cpp:63:5: note: in expansion of macro 'rf'
   63 |     rf
      |     ^~
hac.cpp:6:80: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define rf if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
hac.cpp:63:5: note: in expansion of macro 'rf'
   63 |     rf
      |     ^~

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