Submission #1100856

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1100856	2024-10-14T19:56:57 Z	sano	Mobile (BOI12_mobile)	C++14	100 / 100	416 ms	71088 KB

mobile

#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define shit short double
#define pii pair<long double, long double>
#define NEK 2147483640
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8

using namespace std;

long double bod(pii a, pii b) {
	return (b.first * b.first + b.second * b.second - a.first * a.first - a.second * a.second) / (2 * (b.first - a.first));
}

long double dist(pii a, pii b) {
	return sqrt(abs(a.ff - b.ff) * abs(a.ff - b.ff) + abs(a.ss - b.ss) * (abs(a.ss - b.ss)));
}


int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	long double n, l;
	cin >> n >> l;
	vec<pii> p;
	vec<long double> s;
	For(i, n) {
		long double x, y;
		cin >> x >> y;
		y = abs(y);
		if (!p.empty()) {
			if (p.back().ff == x) {
				if (p.back().ss > y) {
					p.pop_back();
					p.push_back({ x, y });
				}
				continue;
			}
		}
		p.push_back({ x, y });
	}
	For(i, p.size()) {
		while (s.size() > 1 && bod(p[s[s.size() - 2]], p[s.back()]) > bod(p[s.back()], p[i])) s.pop_back();
		s.push_back(i);
	}
	while (s.size() > 1 && bod(p[s[s.size() - 2]], p[s.back()]) > l) s.pop_back();
	long double md = 0; bool prvy = false;
	For(i, (s.size() - 1)) {
		long double hod = bod(p[s[i]], p[s[i + 1]]);
		if (hod < 0) continue;
		if (prvy == false) {
			md = dist(p[s[i]], { 0, 0 });
			prvy = true;
		}
		md = max(md, dist(p[s[i]], { hod, 0 }));
		md = max(md, dist(p[s[i + 1]], { hod, 0 }));
	}
	md = max(md, dist(p[s.back()], { l, 0 }));
	cout << fixed << setprecision(3);
	cout << md << endl;
	return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	592 KB	Output is correct
2	Correct	3 ms	848 KB	Output is correct
3	Correct	2 ms	336 KB	Output is correct
4	Correct	3 ms	848 KB	Output is correct

Subtask #5
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	592 KB	Output is correct
2	Correct	3 ms	848 KB	Output is correct
3	Correct	2 ms	336 KB	Output is correct
4	Correct	3 ms	848 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	848 KB	Output is correct
2	Correct	2 ms	848 KB	Output is correct
3	Correct	2 ms	336 KB	Output is correct
4	Correct	3 ms	848 KB	Output is correct
5	Correct	2 ms	540 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	6600 KB	Output is correct
2	Correct	27 ms	4300 KB	Output is correct
3	Correct	18 ms	4044 KB	Output is correct
4	Correct	31 ms	7880 KB	Output is correct
5	Correct	13 ms	916 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	848 KB	Output is correct
2	Correct	24 ms	4292 KB	Output is correct
3	Correct	31 ms	7624 KB	Output is correct
4	Correct	34 ms	7760 KB	Output is correct
5	Correct	34 ms	7880 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	7876 KB	Output is correct
2	Correct	27 ms	4304 KB	Output is correct
3	Correct	31 ms	8636 KB	Output is correct
4	Correct	41 ms	8136 KB	Output is correct
5	Correct	28 ms	2512 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	4556 KB	Output is correct
2	Correct	34 ms	4812 KB	Output is correct
3	Correct	28 ms	2256 KB	Output is correct
4	Correct	44 ms	8208 KB	Output is correct
5	Correct	36 ms	7880 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	7624 KB	Output is correct
2	Correct	34 ms	4716 KB	Output is correct
3	Correct	27 ms	2256 KB	Output is correct
4	Correct	41 ms	8136 KB	Output is correct
5	Correct	35 ms	7880 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	171 ms	32684 KB	Output is correct
2	Correct	142 ms	5072 KB	Output is correct
3	Correct	146 ms	8140 KB	Output is correct
4	Correct	203 ms	26544 KB	Output is correct
5	Correct	175 ms	24752 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	144 ms	5424 KB	Output is correct
2	Correct	179 ms	25272 KB	Output is correct
3	Correct	139 ms	13752 KB	Output is correct
4	Correct	199 ms	26280 KB	Output is correct
5	Correct	177 ms	23372 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	218 ms	49968 KB	Output is correct
2	Correct	162 ms	776 KB	Output is correct
3	Correct	167 ms	9312 KB	Output is correct
4	Correct	268 ms	46012 KB	Output is correct
5	Correct	199 ms	25944 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	172 ms	6092 KB	Output is correct
2	Correct	224 ms	42572 KB	Output is correct
3	Correct	169 ms	14504 KB	Output is correct
4	Correct	245 ms	45784 KB	Output is correct
5	Correct	220 ms	44192 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	245 ms	50812 KB	Output is correct
2	Correct	197 ms	776 KB	Output is correct
3	Correct	202 ms	10868 KB	Output is correct
4	Correct	280 ms	45744 KB	Output is correct
5	Correct	240 ms	28080 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	205 ms	6728 KB	Output is correct
2	Correct	257 ms	42408 KB	Output is correct
3	Correct	195 ms	16824 KB	Output is correct
4	Correct	296 ms	45480 KB	Output is correct
5	Correct	280 ms	44460 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	279 ms	60800 KB	Output is correct
2	Correct	254 ms	3060 KB	Output is correct
3	Correct	221 ms	12236 KB	Output is correct
4	Correct	324 ms	45736 KB	Output is correct
5	Correct	279 ms	28076 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	234 ms	7756 KB	Output is correct
2	Correct	290 ms	42408 KB	Output is correct
3	Correct	220 ms	17908 KB	Output is correct
4	Correct	323 ms	45736 KB	Output is correct
5	Correct	295 ms	44456 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	353 ms	71088 KB	Output is correct
2	Correct	288 ms	8776 KB	Output is correct
3	Correct	263 ms	15052 KB	Output is correct
4	Correct	396 ms	52648 KB	Output is correct
5	Correct	335 ms	28328 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	292 ms	13896 KB	Output is correct
2	Correct	376 ms	47524 KB	Output is correct
3	Correct	277 ms	26292 KB	Output is correct
4	Correct	416 ms	52640 KB	Output is correct
5	Correct	378 ms	44748 KB	Output is correct

Submission #1100856

Compilation message