oj.uz

Submission #56166

# Submission time Handle Problem Language Result Execution time Memory
56166 2018-07-10T07:03:14 Z 윤교준(#1582) Mobile (BOI12_mobile) C++11
0 / 100
 438 ms 57072 KB 
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<int, ld> pid;

const int MAXN = 1000005;

vector<pid> G;

ll A[MAXN], B[MAXN];
int X[MAXN], Y[MAXN];

ld Ans;
int N, L;

ld f(int i, ld x) { return x*x + x*A[i] + B[i]; }

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> L;
	{
		vector<pii> V;
		for(int i = 0, x, y; i < N; i++) {
			cin >> x >> y;
			V.eb(x, abs(y));
		}
		sorv(V); univ(V);
		
		N = sz(V);
		for(int i = 1; i <= N; i++)
			tie(X[i], Y[i]) = V[i-1];
	}

	for(int i = 1; i <= N; i++) {
		A[i] = ll(X[i]) * (-2);
		B[i] = ll(X[i]) * X[i] + ll(Y[i]) * Y[i];
	}

	for(int i = 1; i <= N; i++) {
		for(; 1 < i && i <= N && A[i-1] == A[i]; i++);
		if(N < i) break;

		for(; !G.empty();) {
			int j; ld X; tie(j, X) = G.back();
			ld x = ld(B[i]-B[j]) / ld(A[i]-A[j]) * (-1);
			if(X < x) {
				G.eb(i, x);
				break;
			}
			G.pop_back();
		}
		if(G.empty()) G.eb(i, ld(0));
	}

	for(int i = 0; i < sz(G); i++) {
		if(!i) upmax(Ans, f(G[0].first, 0));
		if(i+1 == sz(G)) upmax(Ans, f(G.back().first, L));
		upmax(Ans, f(G[i].first, G[i].second));
	}

	printf("%Lf\n", sqrt(Ans));
	return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 6880 KB Output is correct
2 Incorrect 46 ms 6880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 6880 KB Output is correct
2 Incorrect 33 ms 6880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 28900 KB Output is correct
2 Correct 175 ms 28900 KB Output is correct
3 Incorrect 207 ms 28900 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 28900 KB Output is correct
2 Incorrect 201 ms 28900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 47604 KB Output is correct
2 Incorrect 238 ms 47604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 47604 KB Output is correct
2 Incorrect 267 ms 47604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 49988 KB Output is correct
2 Correct 269 ms 49988 KB Output is correct
3 Incorrect 207 ms 49988 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 49988 KB Output is correct
2 Incorrect 280 ms 49988 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 52304 KB Output is correct
2 Correct 317 ms 52304 KB Output is correct
3 Incorrect 257 ms 52304 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 52304 KB Output is correct
2 Incorrect 303 ms 52304 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 57072 KB Output is correct
2 Correct 355 ms 57072 KB Output is correct
3 Correct 322 ms 57072 KB Output is correct
4 Incorrect 390 ms 57072 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 57072 KB Output is correct
2 Incorrect 408 ms 57072 KB Output isn't correct
3 Halted 0 ms 0 KB -