Submission #720597

# Submission time Handle Problem Language Result Execution time Memory
720597 2023-04-08T15:10:42 Z mariowong Balloons (CEOI11_bal) C++14
100 / 100
528 ms 5500 KB
#include <bits/stdc++.h>
using namespace std;

int ptr;
long double sqr(long double a1){
	return a1*a1;	
}
struct ballon{
	long double xx,rr;
}a[200005];
int main(){
	ios::sync_with_stdio(false);
	int n;
	cin >> n;	
	for (int i=1;i<=n;i++){
		long double x,r;
		cin >> x >> r;
		if (i == 1){
			cout << setprecision(3) << fixed << r << "\n";
			a[++ptr]={x,r};	
		}
		else
		{
			long double ans=r;
			while (ptr > 0){
				ans=min(ans,sqr(x-a[ptr].xx)/4.0/a[ptr].rr);	
				if (ans >= a[ptr].rr) ptr--;
				else break;
			}
			cout << setprecision(3) << fixed << ans << "\n";
			a[++ptr]={x,ans};
		}
	}
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB 10 numbers
# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB 2 numbers
# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB 505 numbers
# Verdict Execution time Memory Grader output
1 Correct 8 ms 380 KB 2000 numbers
# Verdict Execution time Memory Grader output
1 Correct 51 ms 680 KB 20000 numbers
# Verdict Execution time Memory Grader output
1 Correct 135 ms 1772 KB 50000 numbers
2 Correct 122 ms 1636 KB 49912 numbers
# Verdict Execution time Memory Grader output
1 Correct 265 ms 2812 KB 100000 numbers
# Verdict Execution time Memory Grader output
1 Correct 312 ms 3316 KB 115362 numbers
2 Correct 366 ms 3392 KB 119971 numbers
# Verdict Execution time Memory Grader output
1 Correct 402 ms 3700 KB 154271 numbers
2 Correct 528 ms 5412 KB 200000 numbers
# Verdict Execution time Memory Grader output
1 Correct 514 ms 3952 KB 200000 numbers
2 Correct 478 ms 5500 KB 199945 numbers