Submission #1222717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222717		i_love_spring	Hacker (BOI15_hac)	C++20	100 / 100	289 ms	18052 KiB

hac

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
void solve() {
  int n;
  cin >> n;
  vector<int> a(n * 2 + 1, 0);
  for (int i = 1; i <= n;i++) cin >> a[i], a[i + n] = a[i];
  for (int i = 1; i <= n * 2;i++) {
    a[i] += a[i - 1];
  } 
  multiset<int>ms;
  vector<int> res(n + 1,1e9+5);
  res[0] = 0;
  int m = (n + 1) / 2;
  for (int i = 1; i <= 2 * n;i++) {
    if (i + m - 1 <= 2 * n) ms.insert(a[i + m - 1] - a[i - 1]);
    if (i > m) ms.erase(ms.find(a[i - 1] - a[i - m - 1]));
    int prev = i % n;
    if (prev == 0) prev = n;
    res[prev] = min(res[prev],*ms.begin());
  }
  cout << *max_element(res.begin(),res.end());
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t = 1;
  //cin >> t;
  while (t--) {
    solve();
    cout << "\n";
  }
  return 0;
} 

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