Submission #1171425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171425		MinhKien	Hacker (BOI15_hac)	C++20	100 / 100	118 ms	10224 KiB

hac

#include <iostream>

using namespace std;

const int N = 5e5 + 10;
const int INF = 1e9;

struct ST {
    int st[N << 2];

    ST () {fill_n(st, N << 2, INF);}

    void update(int l, int r, int u, int v, int val, int id) {
        if (l > v || r < u) return;

        if (l >= u && r <= v) {
            st[id] = min(st[id], val);
            return;
        }

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

    int get(int l, int r, int u, int id) {
        if (l == r) return st[id];

        int m = (l + r) >> 1;
        if (u <= m) return min(st[id], get(l, m, u, id << 1));
        return min(st[id], get(m + 1, r, u, id << 1 | 1));
    }
} seg;

int n, a[N];

int get(int l, int r) {
    if (r > n) return get(l, n) + get(1, r - n);
    return a[r] - a[l - 1];
}

int main() {
    if (fopen("chonso.inp", "r")) {
        freopen("chonso.inp", "r", stdin);
        freopen("chonso.out", "w", stdout);
    }

    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

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

    int len = (n >> 1) + (n & 1);
    for (int i = 1; i <= n; ++i) {
        int r = i + len - 1, val = get(i, i + len - 1);

        if (r > n) {
            seg.update(1, n, i, n, val, 1);
            seg.update(1, n, 1, r - n, val, 1);
        } else {
            seg.update(1, n, i, r, val, 1);
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = max(ans, seg.get(1, n, i, 1));

    cout << ans << "\n";

    return 0;
}

Compilation message (stderr)

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

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