Submission #1171819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171819		julia_08	Hacker (BOI15_hac)	C++20	100 / 100	99 ms	27844 KiB

hac

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAXN = 5e5 + 10;

int v[MAXN], val[MAXN];

int s[MAXN], max_pref[MAXN], max_suf[MAXN];

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);

  int n; cin >> n;

  for(int i=1; i<=n; i++){
    cin >> v[i];

    s[i] = s[i - 1] + v[i];
    val[i] = -1;
  }

  for(int i=1; i<=n; i++){
    if(i >= n / 2){
      max_pref[i] = max(max_pref[i - 1], s[i] - s[i - n / 2]);
    }
  }

  for(int i=n; i>=1; i--){
    if(n - i + 1 >= n / 2){
      max_suf[i] = max(max_suf[i + 1], s[i + n / 2 - 1] - s[i - 1]);
    }
  }

  int ans = -1e9;

  multiset<int> ms;

  for(int i=1; i<=n; i++){

    if(val[i] != -1) ms.erase(ms.find(val[i]));

    int max_sum = max(max_pref[i - 1], max_suf[i + 1]);

    if(!ms.empty()) max_sum = max(max_sum, *ms.rbegin());

    ans = max(ans, s[n] - max_sum);

    int left = (n / 2) - i;

    if(left > 0){
      int sum = s[n] - (s[n - left] - s[i]);
      val[n - left + 1] = sum;
      ms.insert(sum);
    }

  }

  cout << ans << "\n";

  return 0;
}

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