oj.uz

Submission #612393

# Submission time Handle Problem Language Result Execution time Memory
612393 2022-07-29T14:05:37 Z balbit Seesaw (JOI22_seesaw) C++14
1 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>
using namespace std;

#define int ll
#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for(int i = 1; i<=n; ++i)
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif 

const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e5+5;
int a[maxn], ps[maxn];
int n; 

long double cal(long double M) {
	long double rb = 0;
	int x = 0;
	for (int i = n; i>=1;--i) {
		while (ps[x+i]-ps[x] < M * i) {
			++x;
		}
		MX(rb, (ps[x+i] - ps[x]) / (long double) i);
	}
	return rb - M;
}

signed main(){
	ios::sync_with_stdio(0), cin.tie(0);
	bug(1,2);

	cin>>n;


	REP1(i,n) {
		cin>>a[i];
		ps[i] = ps[i-1] + a[i];
	}
	
	long double lb = 0, rb = ps[n] / (long double) n;

	long double re = inf;
	
	REP(round, 100) {
		long double df = (rb - lb) / 3;
		long double m1 = lb + df, m2 = rb - df;
		long double g1 = cal(m1), g2 = cal(m2);
		if (g1 < g2) {
			rb = m2;
		}else {
			lb = m1;
		}
	}

	bug(lb, rb);

	cout<<fixed<<setprecision(12)<<cal(lb)<<endl;


}

Compilation message

seesaw.cpp: In function 'int main()':
seesaw.cpp:57:14: warning: unused variable 're' [-Wunused-variable]
   57 |  long double re = inf;
      |              ^~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -