oj.uz

Submission #612263

# Submission time Handle Problem Language Result Execution time Memory
612263 2022-07-29T12:13:21 Z balbit Seesaw (JOI22_seesaw) C++14
67 / 100
 1014 ms 1048576 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 rbound = -1;
	REP1(len,n) {
		for(int i = 1; i+len-1 <= n; ++i) {
			double me = (ps[i+len-1] - ps[i-1])/(double)len;
			if(i == 1) MX(rbound, me);
			double nxt = (i+len-1<n)?(ps[i+len] - ps[i])/(double)len : inf;
			po.pb({me, nxt});
		}
	}

	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

# 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 1 ms 328 KB Output is correct

Subtask #2
33.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 1 ms 328 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct

Subtask #3
33.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 1 ms 328 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 252 ms 33356 KB Output is correct
9 Correct 273 ms 33264 KB Output is correct
10 Correct 267 ms 33312 KB Output is correct
11 Correct 253 ms 33272 KB Output is correct

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 1 ms 328 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 252 ms 33356 KB Output is correct
9 Correct 273 ms 33264 KB Output is correct
10 Correct 267 ms 33312 KB Output is correct
11 Correct 253 ms 33272 KB Output is correct
12 Runtime error 1014 ms 1048576 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -