oj.uz

Submission #625682

# Submission time Handle Problem Language Result Execution time Memory
625682 2022-08-10T16:58:24 Z AmirAli_H1 Balloons (CEOI11_bal) C++17
100 / 100
 208 ms 14792 KB 
// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

typedef long long int	ll;
typedef long double	ld;

#define all(x)		(x).begin(),(x).end()
#define F		first
#define S		second
#define pb		push_back
#define sep             ' '
#define endl            '\n'
#define Mp		make_pair
#define kill(x)		cout << x << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define file_io(x,y)	freopen(x, "r", stdin); freopen(y, "w", stdout);

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int n;
	cin >> n;
	
	pair<ld, ld> arr[n];
	for (int i = 0; i < n; i++) cin >> arr[i].F >> arr[i].S;
	
	vector<int> st;
	ld ans[n];
	for (int i = 0; i < n; i++) {
		ld r = arr[i].S;
		while (st.size() > 0 && ans[st[st.size() - 1]] <= min(r, pow(arr[i].F - arr[st[st.size() - 1]].F, 2) / (4 * ans[st[st.size() - 1]]))) {
			r = min(r, pow(arr[i].F - arr[st[st.size() - 1]].F, 2) / (4 * ans[st[st.size() - 1]]));
			st.pop_back();
		}
		if (st.size() > 0) {
			r = min(r, pow(arr[i].F - arr[st[st.size() - 1]].F, 2) / (4 * ans[st[st.size() - 1]]));
		}
		ans[i] = r;
		st.pb(i);
	}
	
	set_dec(3);
	for (int i = 0; i < n; i++) {
		cout << ans[i] << endl;
	}
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 416 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1568 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3784 KB 50000 numbers
2 Correct 49 ms 3916 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 7276 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 8524 KB 115362 numbers
2 Correct 119 ms 8968 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 11212 KB 154271 numbers
2 Correct 204 ms 14792 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 13976 KB 200000 numbers
2 Correct 202 ms 14748 KB 199945 numbers