oj.uz

Submission #127098

# Submission time Handle Problem Language Result Execution time Memory
127098 2019-07-08T22:02:54 Z Mahmoud_Adel Mobile (BOI12_mobile) C++14
95 / 100
 1000 ms 83824 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();
		if(t.s.f != 0)
		ans = max(ans, min(dis(t.f, t.s.f), dis(s.top().f, t.s.f)));
		else
		ans = max(ans, dis(t.f, t.s.f));
		if(t.s.s == m) ans = max(ans, 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 380 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 504 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 4 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 504 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 5 ms 504 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 540 KB Output is correct
2 Correct 7 ms 676 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 6 ms 504 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 504 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 64 ms 3472 KB Output is correct
2 Correct 61 ms 3184 KB Output is correct
3 Correct 51 ms 2552 KB Output is correct
4 Correct 65 ms 3088 KB Output is correct
5 Correct 34 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 52 ms 3436 KB Output is correct
3 Correct 60 ms 3960 KB Output is correct
4 Correct 65 ms 4088 KB Output is correct
5 Correct 76 ms 4472 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 8184 KB Output is correct
2 Correct 66 ms 3636 KB Output is correct
3 Correct 82 ms 5296 KB Output is correct
4 Correct 92 ms 4088 KB Output is correct
5 Correct 62 ms 3528 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 4472 KB Output is correct
2 Correct 80 ms 4020 KB Output is correct
3 Correct 74 ms 4316 KB Output is correct
4 Correct 93 ms 4092 KB Output is correct
5 Correct 73 ms 3832 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 5796 KB Output is correct
2 Correct 80 ms 4032 KB Output is correct
3 Correct 75 ms 4344 KB Output is correct
4 Correct 91 ms 4132 KB Output is correct
5 Correct 74 ms 3832 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 41932 KB Output is correct
2 Correct 402 ms 17168 KB Output is correct
3 Correct 384 ms 17044 KB Output is correct
4 Correct 441 ms 16792 KB Output is correct
5 Correct 374 ms 17044 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 17204 KB Output is correct
2 Correct 467 ms 17928 KB Output is correct
3 Correct 374 ms 19220 KB Output is correct
4 Correct 437 ms 16964 KB Output is correct
5 Correct 379 ms 16964 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 603 ms 50016 KB Output is correct
2 Correct 478 ms 20376 KB Output is correct
3 Correct 458 ms 20064 KB Output is correct
4 Correct 540 ms 20088 KB Output is correct
5 Correct 441 ms 20088 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 20372 KB Output is correct
2 Correct 564 ms 21240 KB Output is correct
3 Correct 440 ms 21804 KB Output is correct
4 Correct 534 ms 20088 KB Output is correct
5 Correct 463 ms 20216 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 57976 KB Output is correct
2 Correct 561 ms 23416 KB Output is correct
3 Correct 541 ms 23288 KB Output is correct
4 Correct 637 ms 23312 KB Output is correct
5 Correct 509 ms 23212 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 23544 KB Output is correct
2 Correct 653 ms 24596 KB Output is correct
3 Correct 537 ms 26328 KB Output is correct
4 Correct 626 ms 23232 KB Output is correct
5 Correct 526 ms 23288 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 840 ms 65996 KB Output is correct
2 Correct 645 ms 26612 KB Output is correct
3 Correct 616 ms 26468 KB Output is correct
4 Correct 707 ms 26444 KB Output is correct
5 Correct 596 ms 26408 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 648 ms 26888 KB Output is correct
2 Correct 751 ms 27640 KB Output is correct
3 Correct 596 ms 29304 KB Output is correct
4 Correct 706 ms 26484 KB Output is correct
5 Correct 605 ms 26900 KB Output is correct

Subtask #20
0 / 5.0

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

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 818 ms 34900 KB Output is correct
2 Correct 937 ms 34984 KB Output is correct
3 Correct 781 ms 37500 KB Output is correct
4 Correct 890 ms 31804 KB Output is correct
5 Correct 781 ms 33580 KB Output is correct