Submission #1245732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245732		lopkus	Hacker (BOI15_hac)	C++20	0 / 100	1 ms	2372 KiB

hac

#include <bits/stdc++.h>

const int N = 5e5 + 5;

std::vector<int> pref(N);

int64_t sum(int l, int r) {
  if(l > r) {
    return 0LL;
  }
  else {
    return pref[r] - pref[l - 1];
  }
}

signed main() {
  int n;
  std::cin >> n;
  std::vector<int64_t> a(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  for(int i = 1; i <= n; i++) {
    pref[i] = pref[i - 1] + a[i];
  }
  int64_t ans = 0;
  for(int i = 1; i <= n; i++) {
    int64_t mn = 1e18;
    int k = (n + 1) / 2;
    for(int j = i; j > std::max(1, i - k + 1); j--) {
      mn = std::min(mn, sum(j, i) + sum(i + 1, k + j - 1));
    }
    for(int j = i; j < std::min(n, i + k - 1); j++) {
      mn = std::min(mn, sum(i, j) + sum(j + 1 - k, i - 1));
    }
    if(k > i) {
      for(int j = i; j < std::min(n, i + k - 1); j++) {
        mn = std::min(mn, sum(1, i) + sum(i + 1, j) + sum(j + n - k + 1, n));
      }
    }
    if(k > n - i + 1) {
      for(int j = i; j > std::max(1, i - k + 1); j--) {
        mn = std::min(mn, sum(j, i) + sum(i + 1, n) + sum(1, k - n + j - 1));
      }
    }
    ans = std::max(ans, mn);
  }
  std::cout << ans;
}

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