Submission #310943

#	Time	Username	Problem	Language	Result	Execution time	Memory
310943		Falcon	Hacker (BOI15_hac)	C++17	100 / 100	565 ms	36112 KiB

hac

#pragma GCC optimize("O2")

#include <bits/stdc++.h>

#ifdef DEBUG
#include "debug.hpp"
#endif

using namespace std;

#define all(c)              (c).begin(), (c).end()
#define traverse(c, it)     for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N)           for(int i = 0; i < (N); ++i)
#define rep1(i, N)          for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e)       for(int i = (s); i <= (e); ++i)
#define rep3(i, s, e, d)    for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back


#ifdef DEBUG
#define debug(x...)         { dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals); }
#define light_debug(x)      { dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << "  " << #x << " = " << x << endl; dbg::light = 0; }
#else
#define debug(x...)         42
#define light_debug(x)      42
#endif


template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }

template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

constexpr ll INF{1LL << 50};

class lazy_segtree {
	int N;
	vector<ll> a, lzy;

	void push(int n, int s, int e) {
		ckmin(a[n], lzy[n]);
		if(s != e)
			ckmin(lzy[n << 1], lzy[n]), ckmin(lzy[n << 1 | 1], lzy[n]);
		lzy[n] = INF;
	}

	void update(int n, int s, int e, int l, int r, ll v) {
		push(n, s, e);
		if(r < s || e < l) return;
		
		if(l <= s && e <= r) {
			ckmin(lzy[n], v);
			push(n, s, e);
			return;
		}

		int m = (s + e) >> 1;
		update(n << 1, s, m, l, r, v); update(n << 1 | 1, m + 1, e, l, r, v);
		a[n] = max(a[n << 1], a[n << 1 | 1]);
	}

public:
	
	lazy_segtree(int _N) : N{_N}, a(N << 2, INF), lzy(N << 2, INF) {}

	void update(int l, int r, ll v) { update(1, 0, N - 1, l, r, v); }

	ll query() { return a[1]; }

};

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

#ifdef DEBUG
	freopen("debug", "w", stderr);
#endif
	
	int n; cin >> n;
	vi a(n); rep(i, n) cin >> a[i];

	lazy_segtree seg(n);

	int l{(n + 1) >> 1}, s{a[n - 1]};
	rep(i, l - 1) s += a[i];

	rep(i, n) {
		int j{(i + l - 1) % n};
		s += a[j] - a[(i + n - 1) % n];
		if(j >= i) seg.update(i, j, s);
		else seg.update(i, n - 1, s), seg.update(0, j, s);
	}

	cout << seg.query() << '\n';

#ifdef DEBUG
	dbg::dout << "\nExecution time: " << clock() << "ms\n";
#endif
	return 0;
}

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