Submission #1245723

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

hac

#include <bits/stdc++.h>

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  std::vector<int> pref(n + 2);
  for(int i = 1; i <= n; i++) {
    pref[i] = pref[i - 1] + a[i];
  }
  std::function<int(int, int)> sum = [&] (int l, int r) {
    if(l > r) {
      return 0;
    }
    else {
      return pref[r] - pref[l - 1];
    }
  };
  int ans = 0;
  for(int i = 1; i <= n; i++) {
    int 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 - 2); j++) {
        mn = std::min(mn, sum(1, i) + sum(i, j) + sum(j + n - k + 1, n));
      }
    }
    if(k >= n - i + 1) {
      for(int j = i; j >= std::max(1, i - k + 2); 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;
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:24:14: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   24 |     int mn = 1e18;
      |              ^~~~

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