| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 133185 | 2019-07-20T08:51:57 Z | sealnot123 | Mobile (BOI12_mobile) | C++14 | 254 ms | 41288 KB |
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
const int N = 1000007;
vector<PLL> tower;
bool cmp(PLL a, PLL b){
if(a.x != b.x) return a.x > b.x;
return a.y < b.y;
}
PLL intersect(PLL a, PLL b){
LL A, B;
A = a.y - b.y;
B = b.x - a.x;
if(B < 0) A = -A, B = -B;
return {A, B};
}
vector<PLL> line;
void add(PLL nw){
while(SZ(line)>1){
int a = SZ(line);
if(line[a-1].x == nw.x) return;
PLL tmp1 = intersect(line[a-2], line[a-1]);
PLL tmp2 = intersect(line[a-1], nw);
if((__int128)tmp2.x*(__int128)tmp1.y <= (__int128)tmp1.x*(__int128)tmp2.y) line.pop_back();
else break;
}
line.pb(nw);
}
LD calc(LD a, int b){
return a*line[b].x + line[b].y;
}
LL L;
int n;
int main(){
int i,j;
LL a,b, dist0 = 2e18+2, distL = 2e18+2;
LD ans;
scanf("%d %lld",&n,&L);
for(i=1;i<=n;i++){
scanf("%lld%lld",&a,&b);
dist0 = min(dist0, a*a + b*b);
distL = min(distL, (L-a)*(L-a) + b*b);
if(tower.empty() || tower.back().x != -a*2) tower.pb({-a*2, a*a + b*b});
else tower.back().y = min(tower.back().y, a*a + b*b);
}
ans = (LD)max(dist0, distL);
for(i=1;i<=n;i++) add(tower[i]);
for(i = 0; i < SZ(line)-1; i++){
PLL tmp = intersect(line[i], line[i+1]);
LD tmp2 = (LD)tmp.x/tmp.y;
if(tmp2 < 0 || tmp2 > L) continue;
ans = max(ans, calc(tmp2, i) + tmp2*tmp2);
}
printf("%Lf",sqrt(ans));
return 0;
}
/*
2 10
0 0
11 1
3 10
1 0
5 0
10 0
2 10
-5 3
12 2
*/
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 376 KB | Output is correct |
| 2 | Correct | 2 ms | 252 KB | Output is correct |
| 3 | Correct | 2 ms | 256 KB | Output is correct |
| 4 | Correct | 2 ms | 376 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 376 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 3 ms | 348 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 4 ms | 504 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 504 KB | Output is correct |
| 2 | Correct | 4 ms | 632 KB | Output is correct |
| 3 | Runtime error | 3 ms | 504 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 3 ms | 632 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 21 ms | 2768 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 19 ms | 1152 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 24 ms | 4964 KB | Output is correct |
| 2 | Runtime error | 25 ms | 2668 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 33 ms | 2432 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 35 ms | 4184 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 136 ms | 21048 KB | Output is correct |
| 2 | Runtime error | 121 ms | 1416 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 121 ms | 1720 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 171 ms | 34936 KB | Output is correct |
| 2 | Runtime error | 142 ms | 1424 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 144 ms | 1400 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 185 ms | 36412 KB | Output is correct |
| 2 | Runtime error | 165 ms | 1436 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 166 ms | 1400 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 209 ms | 37980 KB | Output is correct |
| 2 | Runtime error | 187 ms | 1248 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 188 ms | 1400 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 254 ms | 41288 KB | Output is correct |
| 2 | Runtime error | 229 ms | 1400 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 234 ms | 1184 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |