Submission #538310

#	Time	Username	Problem	Language	Result	Execution time	Memory
538310		pawned	Balloons (CEOI11_bal)	C++17	100 / 100	300 ms	8516 KiB

bal

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<double, double> dd;
typedef vector<int> vi;

int main() {
	int N;
	cin>>N;
	double x[N];
	double r[N];
	for (int i = 0; i < N; i++) {
		cin>>x[i]>>r[i];
	}
/*
	cout<<"start: ";
	for (int i = 0; i < N; i++) {
		printf("%.3f ", r[i]);
	}
*/
	stack<dd> s;
	s.push({x[0], r[0]});
	for (int i = 1; i < N; i++) {
//		cout<<"at "<<i<<endl;
		if (s.size() > 0)
			r[i] = min(r[i], (x[i] - s.top().fi) * (x[i] - s.top().fi) / 4 / s.top().se);
		while (s.size() > 0 && s.top().se <= r[i]) {
			s.pop();
			if (s.size() > 0)
				r[i] = min(r[i], (x[i] - s.top().fi) * (x[i] - s.top().fi) / 4 / s.top().se);
		}
		s.push({x[i], r[i]});
//		cout<<"done "<<i<<endl;
	}
	for (int i = 0; i < N; i++) {
		printf("%.3f\n", r[i]);
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10