oj.uz

Submission #832562

# Submission time Handle Problem Language Result Execution time Memory
832562 2023-08-21T11:47:22 Z Lalic Mobile (BOI12_mobile) C++17
100 / 100
 588 ms 35324 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9+7;
const int MAXN = 2e5+5;
 
void solve(){
	int n; double l; cin >> n >> l;
	vector<pair<double, double>> arr(n);
	for(int i=0;i<n;i++) cin >> arr[i].fi >> arr[i].se;

	double lo=0, hi=1e10;
	while(hi-lo>=0.0001){
		double mid=lo+(hi-lo)/2;

		double lim=0;
		for(int i=0;i<n;i++){
			double dist=sqrt(mid*mid-arr[i].se*arr[i].se);
			if(arr[i].fi-dist<=lim) lim=max(lim, arr[i].fi+dist);
		}

		if(lim>=l) hi=mid;
		else lo=mid;
	}

	cout.precision(3);
	cout.setf(ios::fixed);

	cout << lo << "\n";
}
 
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
	// freopen("loan.in","r",stdin);
    // freopen("loan.out","w",stdout);
 
	int tt=1;
	// cin >> tt;
	while(tt--) solve();
	return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 484 KB Output is correct
5 Correct 3 ms 340 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2252 KB Output is correct
2 Correct 36 ms 2544 KB Output is correct
3 Correct 25 ms 1744 KB Output is correct
4 Correct 43 ms 2652 KB Output is correct
5 Correct 23 ms 1492 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2188 KB Output is correct
2 Correct 38 ms 2188 KB Output is correct
3 Correct 54 ms 2600 KB Output is correct
4 Correct 52 ms 2708 KB Output is correct
5 Correct 53 ms 3088 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2256 KB Output is correct
2 Correct 39 ms 2760 KB Output is correct
3 Correct 39 ms 2532 KB Output is correct
4 Correct 70 ms 3784 KB Output is correct
5 Correct 44 ms 2644 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3404 KB Output is correct
2 Correct 50 ms 3296 KB Output is correct
3 Correct 45 ms 2896 KB Output is correct
4 Correct 59 ms 3796 KB Output is correct
5 Correct 53 ms 3040 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3292 KB Output is correct
2 Correct 53 ms 3280 KB Output is correct
3 Correct 45 ms 2912 KB Output is correct
4 Correct 62 ms 3796 KB Output is correct
5 Correct 52 ms 3156 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 12364 KB Output is correct
2 Correct 245 ms 15824 KB Output is correct
3 Correct 234 ms 15304 KB Output is correct
4 Correct 298 ms 17608 KB Output is correct
5 Correct 262 ms 14920 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 16324 KB Output is correct
2 Correct 316 ms 14668 KB Output is correct
3 Correct 226 ms 13896 KB Output is correct
4 Correct 284 ms 17368 KB Output is correct
5 Correct 274 ms 15432 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 14824 KB Output is correct
2 Correct 290 ms 18924 KB Output is correct
3 Correct 314 ms 18284 KB Output is correct
4 Correct 377 ms 21492 KB Output is correct
5 Correct 324 ms 17760 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 19568 KB Output is correct
2 Correct 365 ms 17640 KB Output is correct
3 Correct 275 ms 16488 KB Output is correct
4 Correct 354 ms 21356 KB Output is correct
5 Correct 336 ms 18404 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 17404 KB Output is correct
2 Correct 338 ms 22064 KB Output is correct
3 Correct 330 ms 21388 KB Output is correct
4 Correct 408 ms 24720 KB Output is correct
5 Correct 365 ms 20232 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 22812 KB Output is correct
2 Correct 420 ms 20500 KB Output is correct
3 Correct 325 ms 19588 KB Output is correct
4 Correct 440 ms 24592 KB Output is correct
5 Correct 377 ms 21396 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 19740 KB Output is correct
2 Correct 385 ms 25144 KB Output is correct
3 Correct 396 ms 24364 KB Output is correct
4 Correct 475 ms 28464 KB Output is correct
5 Correct 431 ms 23984 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 26044 KB Output is correct
2 Correct 465 ms 23344 KB Output is correct
3 Correct 373 ms 22308 KB Output is correct
4 Correct 495 ms 28324 KB Output is correct
5 Correct 483 ms 24368 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 24556 KB Output is correct
2 Correct 484 ms 31472 KB Output is correct
3 Correct 494 ms 30440 KB Output is correct
4 Correct 588 ms 35200 KB Output is correct
5 Correct 543 ms 29556 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 32516 KB Output is correct
2 Correct 579 ms 29272 KB Output is correct
3 Correct 476 ms 28276 KB Output is correct
4 Correct 584 ms 35324 KB Output is correct
5 Correct 536 ms 30688 KB Output is correct