oj.uz

Submission #612307

# Submission time Handle Problem Language Result Execution time Memory
612307 2022-07-29T12:53:54 Z 8e7 Seesaw (JOI22_seesaw) C++17
67 / 100
 206 ms 54144 KB 
//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define double long double
#define maxn 2005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<50;
struct frac{
	ll f, s, id;
	frac(){f = s = id = 0;}
	frac(ll a, ll b, ll c){f = a, s = b, id = c;}
	bool operator <(const frac &p) {
		return f * p.s < s * p.f;	
	}
};
bool cmp(const frac &p, const frac &q){
	return p.f * q.s > p.s * q.f;
}
frac operator -(frac &p, frac &q){
	return frac(p.f * q.s - q.f * p.s, p.s * q.s, 0);
}
vector<frac> a[maxn];
ll ind[maxn], p[maxn], pref[maxn];

int main() {
	io
	int n;
	cin >> n;
	for (int i = 0;i < n;i++) {
		cin >> p[i];
		pref[i] = p[i] + (i ? pref[i-1] : 0);
	}
	priority_queue<frac, vector<frac>, bool (*) (const frac&, const frac&) > pq(cmp);
	frac ma(0, 1, 0);
	for (int x = 0;x < n;x++) {
		for (int i = 0;i < x + 1;i++) {
			int j = i + n - 1 - x;	//[i, j]
			a[x].push_back(frac(pref[j] - (i ? pref[i-1] : 0), n - x, x));
			if (i == 0) {
				pq.push(a[x].back());
				if (ma < a[x].back()) ma = a[x].back();
			}
		}
	}
	frac ans(inf, 1, 0);
	while (pq.size()) {
		frac cur = pq.top();pq.pop();
		//debug(cur.f, cur.s, cur.id, ma.f, ma.s);
		frac val = ma - cur;
		if (val < ans) ans = val;
		ind[cur.id]++;
		if (ind[cur.id] < a[cur.id].size()) {
			frac add = a[cur.id][ind[cur.id]];
			if (ma < add) ma = add;
			pq.push(add);
		} else {
			break;
		}
	}
	double out = ((double)ans.f) / ans.s;
	cout << fixed << setprecision(15) << out << "\n";
}

Compilation message

seesaw.cpp: In function 'int main()':
seesaw.cpp:68:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<frac>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   if (ind[cur.id] < a[cur.id].size()) {
      |       ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 488 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 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 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 488 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 186 ms 54072 KB Output is correct
9 Correct 199 ms 54144 KB Output is correct
10 Correct 206 ms 54072 KB Output is correct
11 Correct 198 ms 54072 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 488 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 186 ms 54072 KB Output is correct
9 Correct 199 ms 54144 KB Output is correct
10 Correct 206 ms 54072 KB Output is correct
11 Correct 198 ms 54072 KB Output is correct
12 Runtime error 3 ms 896 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -