oj.uz

Submission #127085

# Submission time Handle Problem Language Result Execution time Memory
127085 2019-07-08T21:30:05 Z Mahmoud_Adel Mobile (BOI12_mobile) C++14
23 / 100
 1000 ms 56872 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()
{
	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(7) << 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 256 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 5 ms 376 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 8 ms 504 KB Output is correct
2 Correct 11 ms 504 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 10 ms 504 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 10 ms 504 KB Output is correct
2 Correct 11 ms 504 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 11 ms 436 KB Output is correct
5 Incorrect 8 ms 504 KB Output isn't correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 2808 KB Output is correct
2 Correct 131 ms 2656 KB Output is correct
3 Correct 99 ms 2060 KB Output is correct
4 Correct 136 ms 2652 KB Output is correct
5 Incorrect 60 ms 1860 KB Output isn't correct

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 2764 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 143 ms 7416 KB Output is correct
2 Correct 138 ms 2872 KB Output is correct
3 Correct 146 ms 4788 KB Output is correct
4 Correct 209 ms 3384 KB Output is correct
5 Correct 127 ms 3052 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 3652 KB Output is correct
2 Correct 168 ms 3452 KB Output is correct
3 Correct 137 ms 3832 KB Output is correct
4 Correct 213 ms 3404 KB Output is correct
5 Correct 159 ms 3632 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 4688 KB Output is correct
2 Correct 168 ms 3484 KB Output is correct
3 Correct 137 ms 3876 KB Output is correct
4 Correct 216 ms 3520 KB Output is correct
5 Correct 160 ms 3500 KB Output is correct

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 40608 KB Output is correct
2 Correct 886 ms 23788 KB Output is correct
3 Correct 838 ms 23416 KB Output is correct
4 Execution timed out 1032 ms 25720 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 982 ms 16124 KB Output is correct
2 Correct 939 ms 17144 KB Output is correct
3 Correct 737 ms 24184 KB Output is correct
4 Execution timed out 1016 ms 25396 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 994 ms 48836 KB Output is correct
2 Execution timed out 1072 ms 28408 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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