oj.uz

Submission #801916

# Submission time Handle Problem Language Result Execution time Memory
801916 2023-08-02T08:25:45 Z fatemetmhr Seesaw (JOI22_seesaw) C++17
67 / 100
 413 ms 591000 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;
	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];
	}
	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 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 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 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Correct 366 ms 196316 KB Output is correct
9 Correct 371 ms 196316 KB Output is correct
10 Correct 348 ms 196312 KB Output is correct
11 Correct 377 ms 196224 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 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Correct 366 ms 196316 KB Output is correct
9 Correct 371 ms 196316 KB Output is correct
10 Correct 348 ms 196312 KB Output is correct
11 Correct 377 ms 196224 KB Output is correct
12 Runtime error 413 ms 591000 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -