Submission #908348

#	Time	Username	Problem	Language	Result	Execution time	Memory
908348		roimu	Balloons (CEOI11_bal)	C++14	30 / 100	494 ms	6816 KiB

bal

//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>
#include <assert.h>

using namespace std;

typedef long long LL;
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

bool f(pair<LL, double> a, pair<LL, double> b) {
	double bound = a.first + 2 * a.second;
	return b.first > bound;
}

double dist(pair<LL, double> a, pair<LL, double> b) {
	double d = abs(a.first - b.first);
	return (d * d) / 4.0000 / a.second;
}

int main() {
	int n; cin >> n;
	vector<pair<LL, double>> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
	}

	vector<double> ans(n);
	ans[0] = a[0].second;
	stack<pair<LL, double>> st;
	st.push(a[0]);
	for (int i = 1; i < n; i++) {
		double rnow = 100000000000;
		//小さいうちは潰し続ける、潰したときの半径を覚えておく
		while (!st.empty() and f(st.top(),a[i])) {
			rnow = min(rnow, dist(st.top(), a[i]));
			st.pop();
		}

		if (!st.empty()) {
			rnow = min(rnow, dist(st.top(), a[i]));
		}
		rnow = min(rnow, a[i].second);
		ans[i] = rnow;
		st.push({ a[i].first,rnow });
	}

	for (int i = 0; i < n; i++) {
		cout << fixed << setprecision(3) << ans[i] << endl;
	}

	return 0;
}

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