Submission #1300086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300086		tranthienphuc2657	Hacker (BOI15_hac)	C++20	100 / 100	100 ms	156596 KiB

hac

// TranThienPhuc2657
// 20 ngay truoc khi toi ki thi Hoc sinh gioi Quoc gia 2025 - 2026, 25/12/2025.
#include <bits/stdc++.h>
using namespace std;
#define file "CHONSO"
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define Sz(x) ((int) (x).size())
#define getBit(mask, i) (((mask) >> (i)) & 1)
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 inf = 2e9 + 7;
const ll linf = 1e18l + 7;
const int mod = 1e9 + 7;
const int N = 5e5 + 5;
const int LOG = 30;

int n, a[N];
ll sum[N + N];
int mid;

struct Range_minimum_queries {
    ll mn[LOG][N + N];

    void init() {
        for (int i = mid; i <= n + n; i++) mn[0][i] = sum[i] - sum[i - mid];
        for (int lg = 1; (1 << lg) <= n + n; lg++) {
            for (int i = 1; i + (1 << lg) <= n + n; i++) {
                mn[lg][i] = min(mn[lg - 1][i], mn[lg - 1][i + (1 << (lg - 1))]);
            }
        }
    }

    ll get(int l, int r) {
        int lg = 31 - __builtin_clz(r - l + 1);
        return min(mn[lg][l], mn[lg][r - (1 << lg) + 1]);
    }
} rmq;

ll res = 0;

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

// init
void init() {
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
    for (int i = 1; i <= n; i++) sum[i + n] = sum[i + n - 1] + a[i];
    mid = (n + 1) / 2;

    rmq.init();
}

// proc
void proc() {
    for (int i = 1; i < mid; i++) maxi(res, rmq.get(i + n, i + n + mid - 1));
    for (int i = mid; i <= n; i++) maxi(res, rmq.get(i, i + mid - 1));
    cout << res;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(file".inp", "r")) {
        freopen(file".inp", "r", stdin);
        freopen(file".out", "w", stdout);
    }

    inp();
    init();
    proc();
    cerr << "Time elapsed: " << TIME << "s.\n";
    return 0;
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen(file".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hac.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen(file".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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