Submission #1207378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207378		lopkus	Mean (info1cup19_mean)	C++20	0 / 100	0 ms	320 KiB

mean

#include <bits/stdc++.h>

void solve() {
  int n;
  std::cin >> n;
  std::vector<int64_t> a(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  std::sort(a.begin() + 1, a.end());
  std::vector<std::vector<int64_t>> dp(n + 1, std::vector<int64_t>(n + 1, 0));
  for(int i = 1; i <= n; i++) {
    dp[i][i] = a[i];
  }
  for(int d = 2; d <= n; d++) {
    for(int l = 1; l + d - 1 <= n; l++) {
      int r = l + d - 1;
      int64_t ans = 0;
      for(int i = l; i < r; i++) {
        dp[l][r] = std::max(dp[l][r], (dp[l][i] + dp[i + 1][r]) / 2);
      }
    }
  }
  std::cout << dp[1][n];
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int t = 1;
  //std::cin >> t;
  while (t--) {
      solve();
  }

  return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70