Submission #783632

#	Time	Username	Problem	Language	Result	Execution time	Memory
783632		raysh07	Hacker (BOI15_hac)	C++17	100 / 100	234 ms	37956 KiB

hac

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve()
{
	int n; cin >> n;
	vector <int> a(2 * n + 1);
	int tot = 0;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		tot += a[i];
		a[i + n] = a[i];
	}

	vector <int> p(2 * n + 1, 0);
	for (int i = 1; i <= 2 * n; i++){
		p[i] = p[i - 1] + a[i];
	}

	vector <int> v(2 * n + 1, 0);
	int x = (n / 2);
	for (int i = 1; i <= 2 * n; i++){
		if (i + x > 2 * n) continue;

		v[i] = p[i + x - 1] - p[i - 1];
	}

	int ans = 0;
	int r;

	multiset <int> st;
	for (int i = 2; i <= n; i++){
	    if (i + n / 2 > n + 1) {
	        r = i;
	        break;
	    }
		st.insert(v[i]);
	}

	int l = 2;

	for (int i = 1; i <= n; i++){
		ans = max(ans, tot - *(--st.end()));

		if (i != n){
			st.insert(v[r++]);
			st.erase(st.find(v[l++]));
		}
	}

	cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;

   // freopen("in",  "r", stdin);
   // freopen("out", "w", stdout);

  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Compilation message (stderr)

hac.cpp: In function 'void Solve()':
hac.cpp:52:19: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |    st.insert(v[r++]);
      |                   ^

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