oj.uz

Submission #801925

# Submission time Handle Problem Language Result Execution time Memory
801925 2023-08-02T08:27:39 Z fatemetmhr Seesaw (JOI22_seesaw) C++17
67 / 100
 407 ms 591048 KB 
// Be name khode //


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

#define all(x) x.begin(), x.end()
#define mp     make_pair
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 2e3 + 5;

int a[maxn5];

struct kasr{
	__int128 up, dw;
	int l, r;
	kasr(){

	}
	kasr(ll u, ll d){
		up = u;
		dw = d;
	}

} av[maxn5 * maxn5], keep[maxn5][maxn5];

bool operator <(kasr a, kasr b){
	return a.up * b.dw < a.dw * b.up;
}

bool operator <=(kasr a, kasr b){
	return a.up * b.dw <= a.dw * b.up;
}

ld operator -(kasr a, kasr b){
	ld ax = a.up, ay = a.dw, bx = b.up, by = b.dw;
	return ax / ay - bx / by;
}

void out(kasr a){
	cout << ld(a.up) << ' ' << ld(a.dw) << ' ' << ld(a.up) / ld(a.dw) << endl;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	int n; cin >> n;
	ll all = 0;
	int pt = 0;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		all += a[i];
		ll sum = 0;
		for(int j = i; j >= 0; j--){
			sum += a[j];
			av[pt].up = sum;
			av[pt].dw = (i - j + 1);
			av[pt].l = j;
			av[pt].r = i;
			keep[i][j] = av[pt];
			pt++;
		}
	}
	sort(av, av + pt);
	kasr lim(all, n);
	kasr mnr = lim;
	ld ans = 1e18;
	int cnt = 0;
	for(int i = 0; i < pt && av[i] <= lim; i++){
		ans = min(ans, mnr - av[i]);
		//cout << i << ' ' << av[i].l << ' ' << av[i].r << ' ' << ans << endl;
		//out(mnr);
		//out(av[i]);
		int v = av[i].r;
		if(v + 1 < n && mnr < keep[v + 1][av[i].l + 1]){
			mnr = keep[v + 1][av[i].l + 1];
			cnt++;
		}
	}
	assert(cnt <= 10 * n);
	cout << setprecision(15) << ans << endl;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 366 ms 196316 KB Output is correct
9 Correct 380 ms 196316 KB Output is correct
10 Correct 353 ms 196264 KB Output is correct
11 Correct 365 ms 196312 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 366 ms 196316 KB Output is correct
9 Correct 380 ms 196316 KB Output is correct
10 Correct 353 ms 196264 KB Output is correct
11 Correct 365 ms 196312 KB Output is correct
12 Runtime error 407 ms 591048 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -