oj.uz

Submission #468775

# Submission time Handle Problem Language Result Execution time Memory
468775 2021-08-29T14:57:33 Z DDTerziev04 Mobile (BOI12_mobile) C++14
100 / 100
 554 ms 28460 KB 
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;

const int MAXN=1e6;
const double MAXL=1e10;

pair<long long, long long> pts[MAXN];

bool CanCover(int n, int m, double l)
{
   double d=0;
   for(int i=0; i<n; i++)
   {
      double x=sqrt(l*l-pts[i].second*pts[i].second);
      if(pts[i].first-x<=d && pts[i].first+x>=d)
      {
         d=pts[i].first+x;
      }
   }

   return d>=m;
}

int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   int n, m;
   cin >> n >> m;

   for(int i=0; i<n; i++)
   {
      cin >> pts[i].first >> pts[i].second;
   }

   double diff=0.001, l=0, r=MAXL, ans;
   while(r-l>=diff)
   {
      double mid=l+(r-l)/2;
      if(CanCover(n, m, mid))
      {
         ans=mid;
         r=mid;
      }
      else
      {
         l=mid;
      }
   }

   cout << fixed << setprecision(4) << ans << "\n";

   return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 276 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1484 KB Output is correct
2 Correct 34 ms 1476 KB Output is correct
3 Correct 22 ms 1164 KB Output is correct
4 Correct 38 ms 1472 KB Output is correct
5 Correct 21 ms 1072 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1532 KB Output is correct
2 Correct 34 ms 1344 KB Output is correct
3 Correct 39 ms 1620 KB Output is correct
4 Correct 40 ms 1484 KB Output is correct
5 Correct 51 ms 1668 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1592 KB Output is correct
2 Correct 34 ms 1516 KB Output is correct
3 Correct 35 ms 1580 KB Output is correct
4 Correct 57 ms 1852 KB Output is correct
5 Correct 40 ms 1612 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1868 KB Output is correct
2 Correct 44 ms 1868 KB Output is correct
3 Correct 41 ms 1860 KB Output is correct
4 Correct 54 ms 1868 KB Output is correct
5 Correct 48 ms 1876 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1860 KB Output is correct
2 Correct 43 ms 1772 KB Output is correct
3 Correct 41 ms 1852 KB Output is correct
4 Correct 56 ms 1744 KB Output is correct
5 Correct 50 ms 1864 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 8248 KB Output is correct
2 Correct 221 ms 15836 KB Output is correct
3 Correct 215 ms 15516 KB Output is correct
4 Correct 271 ms 17636 KB Output is correct
5 Correct 251 ms 14820 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 8172 KB Output is correct
2 Correct 303 ms 8124 KB Output is correct
3 Correct 214 ms 8132 KB Output is correct
4 Correct 269 ms 8088 KB Output is correct
5 Correct 258 ms 8004 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 9680 KB Output is correct
2 Correct 270 ms 9684 KB Output is correct
3 Correct 266 ms 9692 KB Output is correct
4 Correct 337 ms 9696 KB Output is correct
5 Correct 287 ms 9656 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 9796 KB Output is correct
2 Correct 347 ms 9692 KB Output is correct
3 Correct 253 ms 9692 KB Output is correct
4 Correct 333 ms 9664 KB Output is correct
5 Correct 304 ms 9608 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 11260 KB Output is correct
2 Correct 304 ms 11200 KB Output is correct
3 Correct 309 ms 11264 KB Output is correct
4 Correct 409 ms 11208 KB Output is correct
5 Correct 335 ms 11220 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 11212 KB Output is correct
2 Correct 402 ms 11372 KB Output is correct
3 Correct 296 ms 11236 KB Output is correct
4 Correct 368 ms 11260 KB Output is correct
5 Correct 348 ms 11332 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 12836 KB Output is correct
2 Correct 355 ms 25176 KB Output is correct
3 Correct 354 ms 24320 KB Output is correct
4 Correct 437 ms 28460 KB Output is correct
5 Correct 388 ms 23972 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 12720 KB Output is correct
2 Correct 432 ms 12728 KB Output is correct
3 Correct 331 ms 12740 KB Output is correct
4 Correct 429 ms 12784 KB Output is correct
5 Correct 393 ms 12852 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 16068 KB Output is correct
2 Correct 437 ms 15948 KB Output is correct
3 Correct 432 ms 15948 KB Output is correct
4 Correct 544 ms 15948 KB Output is correct
5 Correct 543 ms 16024 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 15876 KB Output is correct
2 Correct 554 ms 15948 KB Output is correct
3 Correct 421 ms 16064 KB Output is correct
4 Correct 537 ms 15948 KB Output is correct
5 Correct 516 ms 15952 KB Output is correct