Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <string>
- //#include <chrono>
- //#include <fstream>
- //#include <bits/stdc++.h>
- #include <math.h>
- #define mp make_pair
- #define pb push_back
- #define eb emplace_back
- #define x first
- #define y second
- #define sz(x) (int)x.size()
- #define all(x) begin(x), end(x)
- #define rall(x) rbegin(x), rend(x)
- #define FOR(i,a,b) for (int i = (a); i < (b); i++)
- #define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> pi;
- typedef pair<ll, ll> pl;
- typedef vector<int> veci;
- typedef vector<bool> vecb;
- typedef vector<vector<int>> vvi;
- typedef vector<vector<bool>> vvb;
- int v, d, n;
- vector<pi> vec;
- int max_len;
- int str_to_int(string str) {
- return ((str[0] - '0') * 10 + str[1] - '0') * 60 + ((str[3] - '0') * 10 + str[4] - '0');
- }
- string int_to_str(int time) {
- return string(to_string(((time / 60) / 10)) + to_string(((time / 60) % 10)) + ':' + to_string(((time - (time / 60) * 60) / 10)) + to_string(((time - (time / 60) * 60) % 10)));
- }
- bool check(double cur) {
- int cnt = 0;
- vector<bool> used(n);
- for (int i = 0; i < n; i++)
- if ((cnt) * d + cur + (double)vec[i].x / v >= vec[i].y) {
- cnt++;
- used[i] = 1;
- }
- for (int i = n - 1; i >= 0; i--)
- if (!used[i] && (cnt) * d + cur + (double)(2 * max_len - vec[i].x) / v >= vec[i].y)
- cnt++;
- return cnt >= n;
- }
- int main() {
- /*ifstream cin("in.txt");
- ofstream cout("out.txt");
- auto start_time = chrono::high_resolution_clock::now();*/
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- cin >> v >> d >> n;
- vec.assign(n, mp(0, 0));
- max_len = 0;
- for (int i = 0; i < n; i++) {
- string s;
- cin >> vec[i].x >> s;
- max_len = max(max_len, vec[i].x);
- vec[i].y = str_to_int(s);
- }
- double l = 0, r = 24 * 60;
- double eps = 0.1;
- while (l + eps < r) {
- double mid = (l + r) / 2.0;
- if (check(mid))
- r = mid;
- else
- l = mid;
- }
- cout << int_to_str(ceil(round(r) + d * n + (double)(2 * max_len) / v)) << "\n";
- /*auto end_time = chrono::high_resolution_clock::now();
- chrono::duration<double> duration = end_time - start_time;
- cout << duration.count() << "\n";
- cin.close();
- cout.close();*/
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment