Submission #612393

#	Time	Username	Problem	Language	Result	Execution time	Memory
612393		balbit	Seesaw (JOI22_seesaw)	C++14	1 / 100	1 ms	212 KiB

seesaw

#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 (stderr)

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

• Subtask 1: 1 / 1
• Subtask 2: 0 / 33
• Subtask 3: 0 / 33
• Subtask 4: 0 / 33