# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
56167 |
2018-07-10T07:06:25 Z |
윤교준(#1582) |
Mobile (BOI12_mobile) |
C++11 |
|
376 ms |
57180 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;
ld pw(ld n) { return n*n; }
const int MAXN = 1000005;
vector<pid> G;
ll A[MAXN], B[MAXN];
int X[MAXN], Y[MAXN];
ld Ans;
int N, L;
ld naive(ld x) {
ld ret = INFLL;
for(int i = 1; i <= N; i++)
upmin(ret, pw(x-X[i]) + pw(ld(Y[i])));
return ret;
}
ld f(int i, ld x) { return x*x + x*A[i] + B[i]; }
void upd(int i, ld x) {
if(x < 0 || ld(L) < x) return;
upmax(Ans, f(i, x));
}
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++)
upd(G[i].first, G[i].second);
upmax(Ans, max(naive(0), naive(L)));
printf("%Lf\n", sqrt(Ans));
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
548 KB |
Output is correct |
3 |
Correct |
1 ms |
548 KB |
Output is correct |
4 |
Correct |
3 ms |
548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
548 KB |
Output is correct |
2 |
Correct |
3 ms |
548 KB |
Output is correct |
3 |
Correct |
2 ms |
548 KB |
Output is correct |
4 |
Correct |
1 ms |
548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
644 KB |
Output is correct |
2 |
Correct |
4 ms |
860 KB |
Output is correct |
3 |
Correct |
4 ms |
860 KB |
Output is correct |
4 |
Correct |
4 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
860 KB |
Output is correct |
2 |
Correct |
5 ms |
872 KB |
Output is correct |
3 |
Correct |
5 ms |
872 KB |
Output is correct |
4 |
Correct |
6 ms |
872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
872 KB |
Output is correct |
2 |
Correct |
5 ms |
872 KB |
Output is correct |
3 |
Correct |
5 ms |
872 KB |
Output is correct |
4 |
Correct |
6 ms |
876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
876 KB |
Output is correct |
2 |
Correct |
4 ms |
876 KB |
Output is correct |
3 |
Correct |
5 ms |
876 KB |
Output is correct |
4 |
Correct |
6 ms |
876 KB |
Output is correct |
5 |
Correct |
5 ms |
876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
2824 KB |
Output is correct |
2 |
Correct |
34 ms |
2824 KB |
Output is correct |
3 |
Correct |
30 ms |
2824 KB |
Output is correct |
4 |
Correct |
52 ms |
2824 KB |
Output is correct |
5 |
Correct |
20 ms |
2824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
2824 KB |
Output is correct |
2 |
Correct |
23 ms |
2824 KB |
Output is correct |
3 |
Correct |
27 ms |
2824 KB |
Output is correct |
4 |
Correct |
45 ms |
2824 KB |
Output is correct |
5 |
Correct |
42 ms |
2824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
6944 KB |
Output is correct |
2 |
Correct |
49 ms |
6944 KB |
Output is correct |
3 |
Correct |
43 ms |
6944 KB |
Output is correct |
4 |
Correct |
39 ms |
6944 KB |
Output is correct |
5 |
Correct |
27 ms |
6944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
6944 KB |
Output is correct |
2 |
Correct |
32 ms |
6944 KB |
Output is correct |
3 |
Correct |
28 ms |
6944 KB |
Output is correct |
4 |
Correct |
40 ms |
6944 KB |
Output is correct |
5 |
Correct |
34 ms |
6944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
6944 KB |
Output is correct |
2 |
Correct |
32 ms |
6944 KB |
Output is correct |
3 |
Correct |
28 ms |
6944 KB |
Output is correct |
4 |
Correct |
40 ms |
6944 KB |
Output is correct |
5 |
Correct |
33 ms |
6944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
156 ms |
28872 KB |
Output is correct |
2 |
Correct |
158 ms |
28872 KB |
Output is correct |
3 |
Correct |
150 ms |
28872 KB |
Output is correct |
4 |
Correct |
216 ms |
28872 KB |
Output is correct |
5 |
Correct |
167 ms |
28872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
160 ms |
28872 KB |
Output is correct |
2 |
Correct |
155 ms |
28872 KB |
Output is correct |
3 |
Correct |
138 ms |
28872 KB |
Output is correct |
4 |
Correct |
184 ms |
28872 KB |
Output is correct |
5 |
Correct |
168 ms |
28872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
198 ms |
47628 KB |
Output is correct |
2 |
Correct |
213 ms |
47628 KB |
Output is correct |
3 |
Correct |
253 ms |
47628 KB |
Output is correct |
4 |
Correct |
234 ms |
47628 KB |
Output is correct |
5 |
Correct |
207 ms |
47628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
211 ms |
47628 KB |
Output is correct |
2 |
Correct |
211 ms |
47628 KB |
Output is correct |
3 |
Correct |
251 ms |
47628 KB |
Output is correct |
4 |
Correct |
228 ms |
47628 KB |
Output is correct |
5 |
Correct |
229 ms |
47628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
337 ms |
50048 KB |
Output is correct |
2 |
Correct |
242 ms |
50048 KB |
Output is correct |
3 |
Correct |
287 ms |
50048 KB |
Output is correct |
4 |
Correct |
267 ms |
50048 KB |
Output is correct |
5 |
Correct |
278 ms |
50048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
227 ms |
50048 KB |
Output is correct |
2 |
Correct |
220 ms |
50048 KB |
Output is correct |
3 |
Correct |
198 ms |
50048 KB |
Output is correct |
4 |
Correct |
266 ms |
50048 KB |
Output is correct |
5 |
Correct |
234 ms |
50048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
296 ms |
52460 KB |
Output is correct |
2 |
Correct |
254 ms |
52460 KB |
Output is correct |
3 |
Correct |
248 ms |
52460 KB |
Output is correct |
4 |
Correct |
339 ms |
52460 KB |
Output is correct |
5 |
Correct |
276 ms |
52460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
254 ms |
52460 KB |
Output is correct |
2 |
Correct |
243 ms |
52460 KB |
Output is correct |
3 |
Correct |
225 ms |
52460 KB |
Output is correct |
4 |
Correct |
315 ms |
52460 KB |
Output is correct |
5 |
Correct |
288 ms |
52460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
350 ms |
57180 KB |
Output is correct |
2 |
Correct |
309 ms |
57180 KB |
Output is correct |
3 |
Correct |
299 ms |
57180 KB |
Output is correct |
4 |
Correct |
376 ms |
57180 KB |
Output is correct |
5 |
Correct |
338 ms |
57180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
318 ms |
57180 KB |
Output is correct |
2 |
Correct |
305 ms |
57180 KB |
Output is correct |
3 |
Correct |
285 ms |
57180 KB |
Output is correct |
4 |
Correct |
375 ms |
57180 KB |
Output is correct |
5 |
Correct |
339 ms |
57180 KB |
Output is correct |