oj.uz

Submission #127091

# Submission time Handle Problem Language Result Execution time Memory
127091 2019-07-08T21:42:09 Z Mahmoud_Adel Mobile (BOI12_mobile) C++14
63 / 100
 997 ms 84216 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(p[i].f == p[t.f].f || 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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

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 744 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 6 ms 632 KB Output is correct

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
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 Incorrect 5 ms 504 KB Output isn't correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 3576 KB Output is correct
2 Correct 61 ms 3832 KB Output is correct
3 Correct 51 ms 2716 KB Output is correct
4 Correct 63 ms 3832 KB Output is correct
5 Incorrect 30 ms 2296 KB Output isn't correct

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 3576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 8056 KB Output is correct
2 Correct 66 ms 4088 KB Output is correct
3 Correct 80 ms 5760 KB Output is correct
4 Correct 91 ms 5368 KB Output is correct
5 Correct 61 ms 4208 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 5112 KB Output is correct
2 Correct 79 ms 4856 KB Output is correct
3 Correct 64 ms 4856 KB Output is correct
4 Correct 91 ms 5368 KB Output is correct
5 Correct 74 ms 4728 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 6264 KB Output is correct
2 Correct 80 ms 4856 KB Output is correct
3 Correct 64 ms 4856 KB Output is correct
4 Correct 92 ms 5424 KB Output is correct
5 Correct 74 ms 4760 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 43180 KB Output is correct
2 Correct 396 ms 18424 KB Output is correct
3 Correct 381 ms 18408 KB Output is correct
4 Correct 444 ms 18428 KB Output is correct
5 Correct 375 ms 18424 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 18344 KB Output is correct
2 Correct 471 ms 19568 KB Output is correct
3 Correct 323 ms 20692 KB Output is correct
4 Correct 436 ms 18424 KB Output is correct
5 Correct 391 ms 18444 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 51172 KB Output is correct
2 Correct 477 ms 21416 KB Output is correct
3 Correct 453 ms 21648 KB Output is correct
4 Correct 541 ms 21580 KB Output is correct
5 Correct 444 ms 21752 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 21508 KB Output is correct
2 Correct 560 ms 22736 KB Output is correct
3 Correct 370 ms 23288 KB Output is correct
4 Correct 536 ms 21676 KB Output is correct
5 Correct 455 ms 21624 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 59348 KB Output is correct
2 Correct 566 ms 24740 KB Output is correct
3 Correct 540 ms 24828 KB Output is correct
4 Correct 621 ms 24784 KB Output is correct
5 Correct 509 ms 24748 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 26360 KB Output is correct
2 Correct 672 ms 25976 KB Output is correct
3 Correct 480 ms 27788 KB Output is correct
4 Correct 694 ms 24696 KB Output is correct
5 Correct 532 ms 24568 KB Output is correct

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 799 ms 67364 KB Output is correct
2 Correct 636 ms 27768 KB Output is correct
3 Correct 597 ms 27768 KB Output is correct
4 Correct 711 ms 27600 KB Output is correct
5 Incorrect 619 ms 27768 KB Output isn't correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 29864 KB Output is correct
2 Correct 744 ms 28864 KB Output is correct
3 Correct 518 ms 30564 KB Output is correct
4 Correct 716 ms 27608 KB Output is correct
5 Correct 604 ms 27488 KB Output is correct

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 997 ms 84216 KB Output is correct
2 Correct 806 ms 33660 KB Output is correct
3 Correct 743 ms 33656 KB Output is correct
4 Correct 888 ms 31864 KB Output is correct
5 Incorrect 766 ms 33656 KB Output isn't correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 828 ms 35320 KB Output is correct
2 Correct 933 ms 34732 KB Output is correct
3 Correct 682 ms 37112 KB Output is correct
4 Correct 903 ms 31880 KB Output is correct
5 Correct 770 ms 33312 KB Output is correct