# Average and Median

unknown
plain_text
a year ago
1.3 kB
5
Indexable
Never
```#include <bits/stdc++.h>
using namespace std;
const int INF = 1010000000;
int main(){
cout << fixed << setprecision(20);
int N;
cin >> N;
vector<int> A(N);
for (int i = 0; i < N; i++){
cin >> A[i];
}
double tv1 = 0, fv1 = INF;
for (int i = 0; i < 50; i++){
double mid = (tv1 + fv1) / 2;
vector<double> B(N);
for (int j = 0; j < N; j++){
B[j] = A[j] - mid;
}
vector<vector<double>> dp(N + 1, vector<double>(2, -INF));
dp[0][1] = 0;
for (int j = 0; j < N; j++){
dp[j + 1][0] = dp[j][1];
dp[j + 1][1] = max(dp[j][0], dp[j][1]) + B[j];
}
if (dp[N][0] > 0 || dp[N][1] > 0){
tv1 = mid;
} else {
fv1 = mid;
}
}
cout << tv1 << endl;
int tv2 = 0, fv2 = INF;
while (fv2 - tv2 > 1){
int mid = (tv2 + fv2) / 2;
vector<vector<int>> dp(N + 1, vector<int>(2, -INF));
dp[0][1] = 0;
for (int i = 0; i < N; i++){
dp[i + 1][0] = dp[i][1];
dp[i + 1][1] = max(dp[i][0], dp[i][1]);
if (A[i] >= mid){
dp[i + 1][1]++;
} else {
dp[i + 1][1]--;
}
}
if (dp[N][0] > 0 || dp[N][1] > 0){
tv2 = mid;
} else {
fv2 = mid;
}
}
cout << tv2 << endl;
}```