제출 #475052

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
475052		hidden1	Hacker (BOI15_hac)	C++14	100 / 100	454 ms	27792 KiB

hac

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define debug(...) cout << "Line: " << __LINE__ << endl; \
    prllDebug(", "#__VA_ARGS__, __VA_ARGS__)
template <typename T>
void prllDebug(const char* name, T&& arg1) { cout << (name + 2) << " = " << arg1 << endl; }
template <typename T, typename... T2>
void prllDebug(const char* names, T&& arg1, T2&&... args) {
    const char* end = strchr(names + 1, ',');
    cout.write(names + 2, end - names - 2) << " = " << arg1 << endl;
    prllDebug(end, args...);
}
 
const ll MAX_N = 5e5 + 10;
ll arr[2 * MAX_N];
ll pref[2 * MAX_N];
ll n;

ll sum(ll l, ll r) {	
	if(l == 0) {
		return -pref[r];
	}
	return -pref[r] + pref[l - 1];
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for(ll i = 0; i < n; i ++) {
		cin >> arr[i];
		pref[i] = pref[n + i] = arr[n + i] = arr[i];
	}
	for(ll i = 1; i < 2 * n; i ++) {
		pref[i] += pref[i - 1];
	}
	ll sz = n / 2;
	multiset<ll> st;
	for(ll j = 0; j < n - sz; j ++) {
		st.insert(sum(j, j + sz - 1));
	}
	ll ret = 0;
	for(ll i = 0; i < n; i ++) {
		// cout << "Currently removing " << sum(i, i + sz - 1) << " and adding " << sum(n - sz + i, n + i) << endl; 
		st.erase(st.find(sum(i, i + sz - 1)));
		st.insert(sum(n - sz + i, n + i - 1));

/*		cout << "For " << i << endl;
		for(auto it : st) {
			cout << it << ", ";
		}
		cout << endl;
*/
		chkmax(ret, pref[n - 1] + *(st.begin()));
	}
	cout << ret << endl;
    return 0;
}

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