This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define double long double
#define maxn 2005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<50;
struct frac{
ll f, s, id;
frac(){f = s = id = 0;}
frac(ll a, ll b, ll c){f = a, s = b, id = c;}
bool operator <(const frac &p) {
return f * p.s < s * p.f;
}
};
bool cmp(const frac &p, const frac &q){
return p.f * q.s > p.s * q.f;
}
frac operator -(frac &p, frac &q){
return frac(p.f * q.s - q.f * p.s, p.s * q.s, 0);
}
vector<frac> a[maxn];
ll ind[maxn], p[maxn], pref[maxn];
int main() {
io
int n;
cin >> n;
for (int i = 0;i < n;i++) {
cin >> p[i];
pref[i] = p[i] + (i ? pref[i-1] : 0);
}
priority_queue<frac, vector<frac>, bool (*) (const frac&, const frac&) > pq(cmp);
frac ma(0, 1, 0);
for (int x = 0;x < n;x++) {
for (int i = 0;i < x + 1;i++) {
int j = i + n - 1 - x; //[i, j]
a[x].push_back(frac(pref[j] - (i ? pref[i-1] : 0), n - x, x));
if (i == 0) {
pq.push(a[x].back());
if (ma < a[x].back()) ma = a[x].back();
}
}
}
frac ans(inf, 1, 0);
while (pq.size()) {
frac cur = pq.top();pq.pop();
//debug(cur.f, cur.s, cur.id, ma.f, ma.s);
frac val = ma - cur;
if (val < ans) ans = val;
ind[cur.id]++;
if (ind[cur.id] < a[cur.id].size()) {
frac add = a[cur.id][ind[cur.id]];
if (ma < add) ma = add;
pq.push(add);
} else {
break;
}
}
double out = ((double)ans.f) / ans.s;
cout << fixed << setprecision(15) << out << "\n";
}
Compilation message (stderr)
seesaw.cpp: In function 'int main()':
seesaw.cpp:68:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<frac>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | if (ind[cur.id] < a[cur.id].size()) {
| ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |