Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- struct frac {
- li a, b;
- frac() { }
- frac(li a, li b): a(a), b(b) { }
- ld value() { return ld(a) / b; }
- };
- inline bool operator<= (const frac& a, const frac& b) { return a.a * b.b <= a.b * b.a; }
- inline bool operator>= (const frac& a, const frac& b) { return a.a * b.b >= a.b * b.a; }
- inline ostream& operator<< (ostream& out, const frac& f) { return out << f.a << "/" << f.b; }
- ld calc(int *a, int n) {
- static li s[N];
- forn(i, n) s[i + 1] = s[i] + a[i];
- auto d = [](int i, int j) { return frac(s[j + 1] - s[i], j + 1 - i); };
- static int phi[N];
- int p = 0, q = 0;
- ld res = -1e100;
- forn(i, n) {
- while (p + 1 < q && d(phi[q - 2], phi[q - 1] - 1) >= d(phi[q - 2], i - 1)) q--;
- phi[q++] = i;
- while (p + 1 < q && d(phi[p], phi[p + 1] - 1) <= d(phi[p], i)) p++;
- res = max(res, d(phi[p], i).value());
- }
- return res;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement