Submission #871004

# Submission time Handle Problem Language Result Execution time Memory
871004 2023-11-09T16:58:33 Z Trisanu_Das Seesaw (JOI22_seesaw) C++17
Compilation error
0 ms 0 KB
#include <bits/stdc++.h>
using namespace std;

int n;
double a[200005], pref[200005], dp[200005][200005], ans;

double rec(double l){
  for(int i = 0; i < n + 1; i++) for(int j = 0; j < n + 1; j++) dp[i][j] = INT_MAX;
  for(int i = 0; i < n; i++) if(a[i] > l) dp[i][i] = a[i];
  for(int ll = 2; ll < n + 1; ll++){
    for(int i = 0; i + ll  - 1 < n; i++){
      int j = i + ll - 1;
      if(pref[j + 1] - pref[i] < l * (j - i + 1)) continue;
      dp[i][j] = (pref[j + 1] - pref[i]) / (j - i + 1);
      dp[i][j] = max(dp[i][j], min(dp[i + 1][j], dp[i][j - 1]));
    }
  }
  return dp[0][n - 1];
}

int main(){
  cin >> n;
  for(int i = 0; i < n; i++) cin >> a[i];
  sort(a, a + n);
  ans = a[n - 1] - a[0];
  pref[0] = a[0];
  for(int i = 1; i < n; i++) pref[i] = pref[i - 1] + a[i];
  for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
      double l = (pref[j + 1] - pref[i]) / (j - i + 1);
      ans = min(ans, rec(l) - l);
    }
  }
  cout << fixed << setprecision(9) << ans << '\n';
}

Compilation message

/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status