제출 #1270625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270625		lmduc270410	Hacker (BOI15_hac)	C++20	100 / 100	58 ms	64840 KiB

hac

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ldb long double
#define pii pair<int, int>
#define bend(v) v.begin(), v.end()
const int N = 1e6 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int base = 311;
const int inf = INT_MAX;
const ll INF = LLONG_MAX;

int n, a[N], pfs[N], v[N];

const int LG = 18;
int st[LG + 5][N];

int get(int l, int r){
	int k = __lg(r - l + 1);
	return min(st[k][l], st[k][r - (1 << k) + 1]);
}

void solve(){
	
	cin>>n;
	for(int i = 1; i <= n; i++) cin>>a[i];
	for(int i = n + 1; i <= 2 * n; i++) a[i] = a[i - n];
	for(int i = 1; i <= 2 * n; i++) pfs[i] = pfs[i - 1] + a[i];

	int k = (n + 1) / 2;
	for(int i = 1; i <= 2 * n - k + 1; i++) v[i] = pfs[i + k - 1] - pfs[i - 1];
	
	int m = n; n = 2 * n - k + 1;
	for(int i = 1; i <= n; i++) st[0][i] = v[i];
	for(int j = 1; j <= LG; j++){
		for(int i = 1; i + (1 << j) - 1 <= n; i++){
			st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
		}
	}

	int ans = -1;
	for(int i = 1; i <= m; i++) ans = max(ans, get(i, i + k - 1));
	cout<<ans;
}

signed main(){
	
	// freopen(".inp", "r", stdin);
	// freopen(".out", "w", stdout);

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

	int tc = 1;
	// cin>>tc;
	while(tc--) solve();
}

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