Submission #127100

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
127100	2019-07-08T22:04:05 Z	Mahmoud_Adel	Mobile (BOI12_mobile)	C++14	95 / 100	1000 ms	81184 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(10) << ans << endl;
}

Subtask #1
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 #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	416 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	376 KB	Output is correct
2	Correct	4 ms	636 KB	Output is correct
3	Correct	3 ms	376 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	504 KB	Output is correct
2	Correct	7 ms	632 KB	Output is correct
3	Correct	5 ms	632 KB	Output is correct
4	Correct	6 ms	504 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	632 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	6 ms	632 KB	Output is correct
3	Correct	5 ms	632 KB	Output is correct
4	Correct	6 ms	632 KB	Output is correct
5	Correct	5 ms	504 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	3576 KB	Output is correct
2	Correct	61 ms	3448 KB	Output is correct
3	Correct	51 ms	2724 KB	Output is correct
4	Correct	63 ms	3452 KB	Output is correct
5	Correct	32 ms	2296 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	3448 KB	Output is correct
2	Correct	51 ms	3072 KB	Output is correct
3	Correct	60 ms	3428 KB	Output is correct
4	Correct	65 ms	3320 KB	Output is correct
5	Correct	75 ms	3704 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	8056 KB	Output is correct
2	Correct	65 ms	3960 KB	Output is correct
3	Correct	80 ms	5524 KB	Output is correct
4	Correct	91 ms	4824 KB	Output is correct
5	Correct	62 ms	3820 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	4600 KB	Output is correct
2	Correct	80 ms	4252 KB	Output is correct
3	Correct	74 ms	4600 KB	Output is correct
4	Correct	91 ms	4856 KB	Output is correct
5	Correct	73 ms	4216 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	5752 KB	Output is correct
2	Correct	79 ms	4344 KB	Output is correct
3	Correct	74 ms	4572 KB	Output is correct
4	Correct	91 ms	4728 KB	Output is correct
5	Correct	74 ms	4208 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	500 ms	42532 KB	Output is correct
2	Correct	396 ms	18168 KB	Output is correct
3	Correct	385 ms	17784 KB	Output is correct
4	Correct	449 ms	17784 KB	Output is correct
5	Correct	374 ms	17784 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	405 ms	17828 KB	Output is correct
2	Correct	476 ms	18788 KB	Output is correct
3	Correct	374 ms	20120 KB	Output is correct
4	Correct	436 ms	17816 KB	Output is correct
5	Correct	381 ms	17656 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	631 ms	50504 KB	Output is correct
2	Correct	483 ms	21240 KB	Output is correct
3	Correct	466 ms	20924 KB	Output is correct
4	Correct	539 ms	20728 KB	Output is correct
5	Correct	449 ms	20856 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	491 ms	21040 KB	Output is correct
2	Correct	569 ms	22016 KB	Output is correct
3	Correct	438 ms	22520 KB	Output is correct
4	Correct	533 ms	20856 KB	Output is correct
5	Correct	508 ms	20984 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	724 ms	58576 KB	Output is correct
2	Correct	562 ms	24300 KB	Output is correct
3	Correct	545 ms	24056 KB	Output is correct
4	Correct	618 ms	24224 KB	Output is correct
5	Correct	511 ms	24056 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	566 ms	24036 KB	Output is correct
2	Correct	654 ms	25112 KB	Output is correct
3	Correct	532 ms	27128 KB	Output is correct
4	Correct	641 ms	23964 KB	Output is correct
5	Correct	531 ms	24056 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	803 ms	66656 KB	Output is correct
2	Correct	642 ms	27476 KB	Output is correct
3	Correct	623 ms	27188 KB	Output is correct
4	Correct	748 ms	27236 KB	Output is correct
5	Correct	611 ms	27092 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	654 ms	27616 KB	Output is correct
2	Correct	750 ms	28212 KB	Output is correct
3	Correct	598 ms	30072 KB	Output is correct
4	Correct	740 ms	27100 KB	Output is correct
5	Correct	604 ms	26292 KB	Output is correct

Subtask #20
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1025 ms	81184 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	815 ms	31696 KB	Output is correct
2	Correct	935 ms	32952 KB	Output is correct
3	Correct	780 ms	35596 KB	Output is correct
4	Correct	881 ms	31844 KB	Output is correct
5	Correct	767 ms	31948 KB	Output is correct

Submission #127100

Compilation message