oj.uz

답안 #612401

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
612401 2022-07-29T14:18:11 Z balbit Seesaw (JOI22_seesaw) C++14
100 / 100
 76 ms 13708 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];

vector<ll> yoi;

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

	int n; cin>>n;

	REP1(i,n) {
		cin>>a[i];
		ps[i] = ps[i-1] + a[i];
	}
	vector<pair<double, double> > po;

	double cen = ps[n] / (double)(n);
	double rbound = cen;

	{
		int x = 0;
		for (int i = n; i>=1;--i) {
			while (x+i<n && (ps[x+i]-ps[x]) * (__int128) n < ps[n] * (__int128)i) {
				++x;
			}
			if (i == n) {
				po.pb({cen, inf});
			}else{
				assert(x>0);
				double prv = (ps[x+i-1] - ps[x-1])/(double)i;

				double ha = (ps[x+i] - ps[x])/(double)i;
				po.pb({prv, ha}); po.pb({ha, inf});
			}
		}

	}

	sort(ALL(po));
	double re = inf;
	for(auto yo : po) {
		MN(re,rbound - yo.f);
		MX(rbound, yo.s);
		if(rbound >= inf -1) break;
	}

	cout<<fixed<<setprecision(12)<<re<<endl;


}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 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
33.0 / 33.0

# 결과 실행 시간 메모리 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 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 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 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 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 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 74 ms 11760 KB Output is correct
13 Correct 64 ms 13688 KB Output is correct
14 Correct 68 ms 13624 KB Output is correct
15 Correct 76 ms 13708 KB Output is correct
16 Correct 65 ms 13708 KB Output is correct