Submission #486572

#	Time	Username	Problem	Language	Result	Execution time	Memory
486572		erlkonig	Balloons (CEOI11_bal)	C++14	100 / 100	259 ms	9284 KiB

bal

// time-limit: 2000
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define ar array
#define fi first
#define se second
#define ii pair <int, int>
#define vt vector
#define pb push_back
#define sz(x) (int)(x).size()
#define reset(a, x) memset(a, x, sizeof(a))

#define F_OR(i, a, b, s) for (auto i=(a); (s)>0?i<=(b):i>=(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, (e)-1, 1)
#define F_OR2(i, e) F_OR(i, 0, (e)-1, 1)
#define F_OR3(i, b, e) F_OR(i, (b), (e), 1)
#define F_OR4(i, b, e, s) F_OR(i, (b), (e), (s))
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define fo(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define each(x, a) for (auto& x: a)
#define END cerr << "\n";
#define endl "\n"

#define error(args...) { \
	string _s = #args; \
	replace(_s.begin(), _s.end(), ',', ' '); \
	stringstream _ss(_s); \
	istream_iterator <string> _it(_ss); \
	err(_it, args); \
}

void err(istream_iterator<string> it) {}

template<typename T, typename... Args> 
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << "=" << a << ", ";
	err(++it, args...);
}

template<class T> void read(T& x) {
	cin >> x;
}

template<class H, class... T> void read(H& h, T&... t) {
	read(h);
	read(t...);
}

template<class A> void write(A x) {
	cout << x;
}

template<class H, class... T> void write(const H& h, const T&... t) { 
	write(h);
	write(t...);
}

void print() {
	write("\n");
}

template<class H, class... T> void print(const H& h, const T&... t) { 
	write(h);
	if(sizeof...(t))
		write(' ');
	print(t...);
}

#define file ""

inline void setIO() {
	//freopen(file".out", "w", stdout); freopen(file".in", "r", stdin);
	cin.tie(0)->sync_with_stdio(0);
}

const long long INF = 2e18;
const int inf = 0x3c3c3c3c, N = 2e5;
stack <pair <ld, ld>> st;
int n;

ld InflateBalloon(ld x, ld r) {
    while (sz(st)) {
        ld x1 = st.top().fi, r1 = st.top().se;
        r = min(r, (x-x1)*(x-x1)/(4*r1));
        if (r > r1) st.pop();
        else break;
    }
    st.push({x, r});
    return r;
}

void solve() {
	cout << fixed << setprecision(6);
    read(n);
    fo(n) {
        ld x, r;
        read(x, r);
        print(InflateBalloon(x, r));
    }
}

int32_t main() {
	setIO();
	int Case = 1;
	//read(Case);
	fo(ttest, 1, Case) {
		//write("Case ", ttest, ": ");
		solve();
	}
}

• 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