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
#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;
}
# 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
# 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
# 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
# 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
# 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
# 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
# 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
# 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
# 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
# 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
# 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
# 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
# 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
# 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
# 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
# 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
# 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
# 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
# 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
# Verdict Execution time Memory Grader output
1 Execution timed out 1025 ms 81184 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 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