Submission #1276608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276608		behesht	Hacker (BOI15_hac)	C++20	100 / 100	225 ms	32508 KiB

hac

#include <bits/stdc++.h>
 
#define d1(x)                cout << #x << " : " << x << endl << flush
#define d2(x, y)             cout << #x << " : " << x << "   " << #y << " : " << y << endl << flush
#define d3(x, y, z)          cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << endl << flush
#define d4(x, y, z, a)       cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << "    "<< #a << " : " << a << endl << flush
#define arr(x)               array <ll, x>
#define ld                   long double
#define ll                   long long
#define int                  long long
#define pb                   push_back
#define endl                 '\n'
#define lc                   v << 1
#define rc                   v << 1 | 1
 
using namespace std;
 
const int INF = 1e18 + 24 + (34 / 10); // 34 ---> 35
const int MAXN = 1e6 + 24 + (34 / 10); // 34 ---> 35
 
int a[MAXN], ps[MAXN], ns;
 
struct nude{
	int mn;
} sag[MAXN << 2];
 
void bld(int v = 1, int ls = 1, int rs = ns){
	sag[v].mn = INF;
 
	if(ls == rs)
		return;
 
	int m = (rs + ls) >> 1;
	bld(lc, ls, m);
	bld(rc, m + 1, rs);
}
 
void upd(int l, int r, int val, int v = 1, int ls = 1, int rs = ns){
 
	if(l <= ls && rs <= r){
		sag[v].mn = min(sag[v].mn, val);
		return;
	}
 
	if(rs < l || r < ls)
		return;
 
	int m = (rs + ls) >> 1;
 
	upd(l, r, val, lc, ls, m);
	upd(l, r, val, rc, m + 1, rs);
}
 
int get(int ind, int v = 1, int ls = 1, int rs = ns){
 
	if(ls == rs)
		return sag[v].mn;
 
	int m = (rs + ls) >> 1;
 
	if(ind <= m)
		return min(get(ind, lc, ls, m), sag[v].mn);
 
	else 
		return min(get(ind, rc, m + 1, rs), sag[v].mn);
}
 
signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int n;
	cin >> n;
 
	ns = 1;
 
	while(ns < (2 * n))
		ns <<= 1;
	
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		a[i + n] = a[i];
	}
 
	for(int i = 1; i <= (2 * n); i++){
		ps[i] = ps[i - 1] + a[i];
	}
 
	bld();
	// d1(0);
	for(int l = 1; l <= n; l++){
		int r = (n + 1) / 2 + l - 1;
		int sum = ps[r] - ps[l - 1];
 
		upd(l, r, sum);
	}
 
	int ans = 0;
	// d1(1);
	for(int i = 1; i <= n; i++)
		ans = max(ans, min(get(i), get(i + n)));
 
	cout << ans << endl;
}
 
// Ey To Bahane! :_)))
 
// -------------<3------------- //
/*
Magasan dor shirini: 
 
1. MAXN
2. Input style
3. index or value? Masale In Ast!	
4. MOD 
 
*/

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