Submission #1270634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270634		khoianh	Hacker (BOI15_hac)	C++20	100 / 100	166 ms	32508 KiB

hac

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mn = 1e6 + 5;
ll n, a[mn], p[mn], t, st[4 * mn];

void build(ll l, ll r, ll ind){
	if(l == r){
		st[ind] = p[l + t - 1] - p[l - 1];
		return;
	}
	ll mid = (l + r) / 2;
	build(l, mid, ind * 2);
	build(mid + 1, r, ind * 2 + 1);
	st[ind] = min(st[ind * 2], st[ind * 2 + 1]);
	return;
}

ll get(ll l, ll r, ll tl, ll tr, ll ind){
	if(r < tl || tr < l) return 1e18;
	if(tl <= l && r <= tr) return st[ind];
	ll mid = (l + r) / 2;
	return min(get(l, mid, tl, tr, ind * 2), get(mid + 1, r, tl, tr, ind * 2 + 1));
}

void solve(){
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	for(int i = 1; i <= n; ++i) a[i + n] = a[i];
	for(int i = 1; i <= 2 * n; ++i) p[i] = a[i] + p[i - 1];
	t = (n + 1) / 2;
	build(1, 2 * n - t + 1, 1);
	ll ans = 0;
	for(ll i = 1; i <= 2 * n; ++i){
		if(i - t  + 1 < 1 || i > 2 * n - t + 1) continue;
		ans = max(ans, get(1, 2 * n - t + 1, i - t + 1, i, 1));
	}
	cout << ans;
    return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	if(fopen(".INP", "r")) {
		freopen(".INP", "r", stdin);
		freopen(".OUT", "w", stdout);
	}
	int testCase = 1;
	//cin >> testCase;
	while(testCase--) solve();
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:46:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |                 freopen(".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~
hac.cpp:47:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |                 freopen(".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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