oj.uz

Submission #864876

# Submission time Handle Problem Language Result Execution time Memory
864876 2023-10-23T17:21:33 Z MisterReaper Planine (COCI21_planine) C++17
30 / 110
 2000 ms 3628 KB 
//author: Ahmet Alp Orakci
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64

#define ONLINE_JUDGE
void solve() {
	int n, h;
	cin >> n >> h;

	pair <int, int> arr[n];
	for(auto &[a, b] : arr)
		cin >> a >> b;

	vector <pair <double, double>> anss;
	for(int i = 2; i < n -2; i += 2) {
		pair <double, double> ans = {-1E6, 1E6};
		for(int j = 1; j < n; j += 2) {
			if(arr[j].second >= arr[i].second) {
				if(arr[j].first <= arr[i].first) {
					double calc = arr[i].first - double(arr[i].first - arr[j].first) * double(h - arr[i].second) / double(arr[j].second - arr[i].second);
					ans.first = max(ans.first, calc);
				} else {
					double calc = arr[i].first + double(arr[j].first - arr[i].first) * double(h - arr[i].second) / double(arr[j].second - arr[i].second);
					ans.second = min(ans.second, calc);
				}
			}
		}

		anss.push_back(ans);
	}

	sort(anss.begin(), anss.end());

	int cev = 0;
	for(int i = 0; i < int(anss.size()); i++) {
		pair <double, double> nw = anss[i];
		while(i < int(anss.size())) {
			nw.first = max(nw.first, anss[i].first);
			nw.second = min(nw.second, anss[i].second);
			//cerr << anss[i].first << " " << anss[i].second << "\n";
			if(nw.first > nw.second) {
				i--;
				break;
			}

			i++;
		}

		cev++;
	}

	cout << cev << "\n";
	
	return;
}

signed main() {
	#ifndef ONLINE_JUDGE
		freopen(".in", "r", stdin);
		freopen(".out", "w", stdout);
	#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int t = 1; //cin >> t;
	for(int i = 1; i <= t; i++) {
		solve();
	}

	return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 852 KB Output is correct
2 Correct 62 ms 852 KB Output is correct
3 Correct 71 ms 852 KB Output is correct
4 Execution timed out 2019 ms 3628 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 548 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 852 KB Output is correct
2 Correct 62 ms 852 KB Output is correct
3 Correct 71 ms 852 KB Output is correct
4 Execution timed out 2019 ms 3628 KB Time limit exceeded
5 Halted 0 ms 0 KB -