Submission #127101

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
127101	2019-07-08T22:05:36 Z	Mahmoud_Adel	Mobile (BOI12_mobile)	C++14	100 / 100	998 ms	81508 KB

mobile

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long ll;
const int N = 1e6+5;
int n, m;
pair<long double, long double> p[N];
stack<pair<int, pair<long double, long double>>> s;
long double dis(int i, long double x)
{
	long double y = 0;
	return hypot((x-p[i].f), (y-p[i].s));
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i=0; i<n; i++) cin >> p[i].f >> p[i].s;
	for(int i=0; i<n; i++)
	{
		if(s.empty()) s.push({i, {0, m}});
		else
		{
			auto t = s.top();
			if(dis(t.f, t.s.s) < dis(i, t.s.s)) 
			continue;
			long double x;
			while(!s.empty() && dis(s.top().f, s.top().s.f) >= dis(i, s.top().s.f)) x = s.top().s.f, s.pop();
			if(s.empty())
			{ 
				s.push({i, {0, m}});
				continue;
			}
			t = s.top();
			if(dis(t.f, t.s.s) >= dis(i, t.s.s))
			{
				long double x1 = p[i].f, x2 = p[t.f].f;
				long double y1 = p[i].s, y2 = p[t.f].s;
				x = (x1*x1 - x2*x2 + y1*y1-y2*y2)/(2*x1-2*x2);
				if(x <= t.s.f) continue;
				s.pop();
				t.s.s = x;
				s.push(t);
			}
			s.push({i, {x, m}});
		}
	}
	long double ans = 0;
	while(!s.empty())
	{
		auto t = s.top();
		s.pop();
		ans = max(ans, max(dis(t.f, t.s.f), dis(t.f, t.s.s)));
	}
	cout << fixed << setprecision(7) << ans << endl;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	632 KB	Output is correct
2	Correct	7 ms	560 KB	Output is correct
3	Correct	5 ms	632 KB	Output is correct
4	Correct	6 ms	632 KB	Output is correct

Subtask #5
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	504 KB	Output is correct
2	Correct	7 ms	560 KB	Output is correct
3	Correct	5 ms	632 KB	Output is correct
4	Correct	6 ms	632 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	632 KB	Output is correct
2	Correct	7 ms	632 KB	Output is correct
3	Correct	5 ms	504 KB	Output is correct
4	Correct	6 ms	632 KB	Output is correct
5	Correct	5 ms	508 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	3196 KB	Output is correct
2	Correct	61 ms	3320 KB	Output is correct
3	Correct	52 ms	2396 KB	Output is correct
4	Correct	63 ms	3320 KB	Output is correct
5	Correct	32 ms	2168 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	3064 KB	Output is correct
2	Correct	52 ms	3084 KB	Output is correct
3	Correct	60 ms	3192 KB	Output is correct
4	Correct	65 ms	3192 KB	Output is correct
5	Correct	75 ms	3320 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	91 ms	7712 KB	Output is correct
2	Correct	65 ms	3320 KB	Output is correct
3	Correct	80 ms	5280 KB	Output is correct
4	Correct	91 ms	4088 KB	Output is correct
5	Correct	61 ms	3576 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	3832 KB	Output is correct
2	Correct	79 ms	4120 KB	Output is correct
3	Correct	74 ms	4408 KB	Output is correct
4	Correct	91 ms	4088 KB	Output is correct
5	Correct	74 ms	3960 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	101 ms	5112 KB	Output is correct
2	Correct	79 ms	3964 KB	Output is correct
3	Correct	74 ms	4388 KB	Output is correct
4	Correct	92 ms	4088 KB	Output is correct
5	Correct	74 ms	4020 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	503 ms	41380 KB	Output is correct
2	Correct	401 ms	16896 KB	Output is correct
3	Correct	395 ms	16888 KB	Output is correct
4	Correct	473 ms	17092 KB	Output is correct
5	Correct	383 ms	16892 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	412 ms	16792 KB	Output is correct
2	Correct	470 ms	17900 KB	Output is correct
3	Correct	371 ms	19196 KB	Output is correct
4	Correct	439 ms	16956 KB	Output is correct
5	Correct	381 ms	16896 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	601 ms	49508 KB	Output is correct
2	Correct	501 ms	20120 KB	Output is correct
3	Correct	466 ms	20216 KB	Output is correct
4	Correct	534 ms	20144 KB	Output is correct
5	Correct	444 ms	20088 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	487 ms	19864 KB	Output is correct
2	Correct	562 ms	20992 KB	Output is correct
3	Correct	440 ms	21712 KB	Output is correct
4	Correct	533 ms	20088 KB	Output is correct
5	Correct	456 ms	20028 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	706 ms	57520 KB	Output is correct
2	Correct	556 ms	23164 KB	Output is correct
3	Correct	543 ms	23160 KB	Output is correct
4	Correct	636 ms	23292 KB	Output is correct
5	Correct	521 ms	23032 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	574 ms	23164 KB	Output is correct
2	Correct	651 ms	24312 KB	Output is correct
3	Correct	540 ms	26236 KB	Output is correct
4	Correct	616 ms	23176 KB	Output is correct
5	Correct	529 ms	23180 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	800 ms	65636 KB	Output is correct
2	Correct	637 ms	26280 KB	Output is correct
3	Correct	620 ms	26364 KB	Output is correct
4	Correct	709 ms	26360 KB	Output is correct
5	Correct	604 ms	26360 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	648 ms	26236 KB	Output is correct
2	Correct	753 ms	27512 KB	Output is correct
3	Correct	609 ms	29432 KB	Output is correct
4	Correct	706 ms	26204 KB	Output is correct
5	Correct	614 ms	26236 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	998 ms	81508 KB	Output is correct
2	Correct	806 ms	35316 KB	Output is correct
3	Correct	777 ms	35192 KB	Output is correct
4	Correct	878 ms	31892 KB	Output is correct
5	Correct	752 ms	35188 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	946 ms	32356 KB	Output is correct
2	Correct	927 ms	33380 KB	Output is correct
3	Correct	777 ms	35960 KB	Output is correct
4	Correct	891 ms	31864 KB	Output is correct
5	Correct	762 ms	31992 KB	Output is correct

Submission #127101

Compilation message