Submission #1232622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232622		rcll	Hacker (BOI15_hac)	C++20	100 / 100	298 ms	18028 KiB

hac

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a(2*n+1);
	a[0]=0;
	multiset<int> vals;
	int SZ=(n+1)/2;
	for (int i=1; i<=n; i++) {
		cin >> a[i];
		a[n+i]=a[i];
	}
	for (int i=1; i<=2*n; i++) {
        a[i]+=a[i-1];
    }
	int ans=0;
	vector<int> ret(n+1, INT_MAX);
	for (int i=1; i<=2*n; i++) {
		if (i+SZ-1<=2*n) { 
            vals.insert(a[i+SZ-1]-a[i-1]); 
        }
		if (i > SZ) { 
            vals.erase(vals.find(a[i-1]-a[i-1-SZ]));
        }
		int prev=((i-1) % n)+1;
		ret[prev]=min(ret[prev], *vals.begin());
	}
	for (int i=1; i<=n; i++) {
        ans=max(ans, ret[i]);
    }
	cout << ans << '\n';
}

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