Submission #310943

#TimeUsernameProblemLanguageResultExecution timeMemory
310943FalconHacker (BOI15_hac)C++17
100 / 100
565 ms36112 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...