oj.uz

Submission #801926

# Submission time Handle Problem Language Result Execution time Memory
801926 2023-08-02T08:28:14 Z fatemetmhr Seesaw (JOI22_seesaw) C++17
67 / 100
 416 ms 591056 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 <= 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 2 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 2 ms 1096 KB Output is correct
7 Correct 2 ms 1108 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 2 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 2 ms 1096 KB Output is correct
7 Correct 2 ms 1108 KB Output is correct
8 Correct 416 ms 196356 KB Output is correct
9 Correct 385 ms 196320 KB Output is correct
10 Correct 364 ms 196300 KB Output is correct
11 Correct 369 ms 196316 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 2 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 2 ms 1096 KB Output is correct
7 Correct 2 ms 1108 KB Output is correct
8 Correct 416 ms 196356 KB Output is correct
9 Correct 385 ms 196320 KB Output is correct
10 Correct 364 ms 196300 KB Output is correct
11 Correct 369 ms 196316 KB Output is correct
12 Runtime error 396 ms 591056 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -