Submission #872488

#	Time	Username	Problem	Language	Result	Execution time	Memory
872488		sleepntsheep	Balloons (CEOI11_bal)	C++17	100 / 100	156 ms	9296 KiB

bal

#include <iostream>
#include <cassert>
#include <iomanip> 
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using i64 = long long;
using u64 = unsigned long long;
using f80 = long double;

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 200005


int n, x[N];
f80 r[N];

struct Line {
	mutable f80 k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(i64 x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	const f80 inf = f80(1)/0;
    f80 div(f80 a, f80 b) { return a/b;}
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(f80 k, f80 m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	f80 query(i64 x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
} lc;


int main()
{
    ShinLena;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> x[i] >> r[i];

    f80 twoa = 2L * sqrtl(r[0]);
    lc.add(-1 / twoa, x[0] / twoa);

    for (int i = 1; i < n; ++i)
    {
        f80 j = lc.query(x[i]);
        r[i] = min(r[i], j * j);

        f80 twoa = 2L * sqrtl(r[i]);
        lc.add(-1 / twoa, x[i] / twoa);
    }

    cout << fixed << setprecision(3);
    for (int i = 0; i < n; ++i)
        cout << r[i] << '\n';

    return 0;
}

Compilation message (stderr)

bal.cpp:34:24: warning: division by zero [-Wdiv-by-zero]
   34 |  const f80 inf = f80(1)/0;
      |                  ~~~~~~^~

• 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