oj.uz

Submission #462077

# Submission time Handle Problem Language Result Execution time Memory
462077 2021-08-10T07:44:53 Z shivensinha4 Mobile (BOI12_mobile) C++17
100 / 100
 779 ms 110704 KB 
#include <bits/stdc++.h>

#ifdef mlocal
#include "./Competitive-Code-Library/snippets/prettyprint.h"
#endif
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<ll, 2> ii;
typedef pair<double, double> pdd;
#define endl '\n'

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

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && 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(ll k, ll 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));
	}
	
	ll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};

long double calc(Line &l, long double x) {
	return x*x - (l.k * x + l.m);
}

int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	ll l;
	cin >> n >> l;
	vector <ii> pts(n);
	for_(i, 0, n) cin >> pts[i][0] >> pts[i][1];
	
	LineContainer lc;
	for_(i, 0, n) {
		lc.add(2 * pts[i][0], -pts[i][0] * pts[i][0] - pts[i][1] * pts[i][1]);
	}
	
	vector <Line> opt(lc.begin(), lc.end());
	long double ans = -lc.query(0);
	
	for_(i, 1, opt.size()) {
		long double num = (opt[i - 1].m - opt[i].m), den = (opt[i].k - opt[i - 1].k);
		long double intersect = num/den;
		if (intersect < 0 or intersect > l) continue;
		ans = max(ans, calc(opt[i-1], intersect));
//		cout << setprecision(10) << (intersect*intersect + -(opt[i-1].k * intersect + opt[i-1].m)) << endl;
//		cout << intersect << endl;
	}
	
	ans = max(ans, ((long double)l)*l - lc.query(l));
//	cout << ans << endl;
	cout << fixed << setprecision(8) << sqrtl(ans) << endl;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 588 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 3 ms 460 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 2 ms 452 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 332 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2832 KB Output is correct
2 Correct 25 ms 2612 KB Output is correct
3 Correct 18 ms 1788 KB Output is correct
4 Correct 27 ms 2640 KB Output is correct
5 Correct 14 ms 1484 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2292 KB Output is correct
2 Correct 24 ms 2240 KB Output is correct
3 Correct 27 ms 2628 KB Output is correct
4 Correct 28 ms 2756 KB Output is correct
5 Correct 32 ms 3160 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 9872 KB Output is correct
2 Correct 29 ms 2788 KB Output is correct
3 Correct 53 ms 8928 KB Output is correct
4 Correct 40 ms 3788 KB Output is correct
5 Correct 29 ms 2660 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3420 KB Output is correct
2 Correct 33 ms 3264 KB Output is correct
3 Correct 54 ms 4092 KB Output is correct
4 Correct 39 ms 3848 KB Output is correct
5 Correct 34 ms 3144 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 8748 KB Output is correct
2 Correct 35 ms 3264 KB Output is correct
3 Correct 49 ms 4216 KB Output is correct
4 Correct 43 ms 3848 KB Output is correct
5 Correct 34 ms 3156 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 55492 KB Output is correct
2 Correct 159 ms 15816 KB Output is correct
3 Correct 209 ms 15300 KB Output is correct
4 Correct 199 ms 17716 KB Output is correct
5 Correct 176 ms 14912 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 16320 KB Output is correct
2 Correct 231 ms 19228 KB Output is correct
3 Correct 293 ms 22052 KB Output is correct
4 Correct 198 ms 17508 KB Output is correct
5 Correct 208 ms 15420 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 66516 KB Output is correct
2 Correct 189 ms 18968 KB Output is correct
3 Correct 212 ms 18392 KB Output is correct
4 Correct 279 ms 21584 KB Output is correct
5 Correct 243 ms 17756 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 19348 KB Output is correct
2 Correct 269 ms 22480 KB Output is correct
3 Correct 371 ms 22272 KB Output is correct
4 Correct 234 ms 21468 KB Output is correct
5 Correct 218 ms 18400 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 77500 KB Output is correct
2 Correct 225 ms 22084 KB Output is correct
3 Correct 229 ms 21432 KB Output is correct
4 Correct 282 ms 24840 KB Output is correct
5 Correct 260 ms 20340 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 21168 KB Output is correct
2 Correct 308 ms 25588 KB Output is correct
3 Correct 463 ms 30424 KB Output is correct
4 Correct 283 ms 24692 KB Output is correct
5 Correct 272 ms 21488 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 88608 KB Output is correct
2 Correct 327 ms 25232 KB Output is correct
3 Correct 257 ms 24468 KB Output is correct
4 Correct 329 ms 28568 KB Output is correct
5 Correct 295 ms 23960 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 22956 KB Output is correct
2 Correct 366 ms 28812 KB Output is correct
3 Correct 500 ms 32768 KB Output is correct
4 Correct 333 ms 28304 KB Output is correct
5 Correct 299 ms 24484 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 779 ms 110704 KB Output is correct
2 Correct 317 ms 31488 KB Output is correct
3 Correct 332 ms 30408 KB Output is correct
4 Correct 402 ms 35168 KB Output is correct
5 Correct 362 ms 29580 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 22932 KB Output is correct
2 Correct 440 ms 34860 KB Output is correct
3 Correct 679 ms 41448 KB Output is correct
4 Correct 453 ms 35288 KB Output is correct
5 Correct 371 ms 30780 KB Output is correct