Raslboyy

894

Nov 18th, 2019
173
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.30 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5. //#include <chrono>
  6. //#include <fstream>
  7. //#include <bits/stdc++.h>
  8. #include <math.h>
  9.  
  10. #define mp make_pair
  11. #define pb push_back
  12. #define eb emplace_back
  13. #define x first
  14. #define y second
  15. #define sz(x) (int)x.size()
  16. #define all(x) begin(x), end(x)
  17. #define rall(x) rbegin(x), rend(x)
  18. #define FOR(i,a,b) for (int i = (a); i < (b); i++)
  19. #define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
  20.  
  21. using namespace std;
  22.  
  23. typedef unsigned long long ull;
  24. typedef long long ll;
  25. typedef long double ld;
  26. typedef pair<int, int> pi;
  27. typedef pair<ll, ll> pl;
  28. typedef vector<int> veci;
  29. typedef vector<bool> vecb;
  30. typedef vector<vector<int>> vvi;
  31. typedef vector<vector<bool>> vvb;
  32.  
  33. int v, d, n;
  34. vector<pi> vec;
  35. int max_len;
  36.  
  37. int str_to_int(string str) {
  38.     return ((str[0] - '0') * 10 + str[1] - '0') * 60 + ((str[3] - '0') * 10 + str[4] - '0');
  39. }
  40.  
  41. string int_to_str(int time) {
  42.     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)));
  43. }
  44.  
  45. bool check(double cur) {
  46.     int cnt = 0;
  47.     vector<bool> used(n);
  48.     for (int i = 0; i < n; i++)
  49.         if ((cnt) * d + cur + (double)vec[i].x / v >= vec[i].y) {
  50.             cnt++;
  51.             used[i] = 1;
  52.         }
  53.     for (int i = n - 1; i >= 0; i--)
  54.         if (!used[i] && (cnt) * d + cur + (double)(2 * max_len - vec[i].x) / v >= vec[i].y)
  55.             cnt++;
  56.     return cnt >= n;
  57. }
  58.  
  59. int main() {
  60.     /*ifstream cin("in.txt");
  61.     ofstream cout("out.txt");
  62.     auto start_time = chrono::high_resolution_clock::now();*/
  63.  
  64.     ios::sync_with_stdio(false);
  65.     cin.tie(0);
  66.     cout.tie(0);
  67.  
  68.    
  69.     cin >> v >> d >> n;
  70.     vec.assign(n, mp(0, 0));
  71.     max_len = 0;
  72.     for (int i = 0; i < n; i++) {
  73.         string s;
  74.         cin >> vec[i].x >> s;
  75.         max_len = max(max_len, vec[i].x);
  76.         vec[i].y = str_to_int(s);
  77.     }
  78.    
  79.     double l = 0, r = 24 * 60;
  80.     double eps = 0.1;
  81.     while (l + eps < r) {
  82.         double mid = (l + r) / 2.0;
  83.         if (check(mid))
  84.             r = mid;
  85.         else
  86.             l = mid;
  87.     }
  88.     cout << int_to_str(ceil(round(r) + d * n + (double)(2 * max_len) / v)) << "\n";
  89.  
  90.    
  91.     /*auto end_time = chrono::high_resolution_clock::now();
  92.     chrono::duration<double> duration = end_time - start_time;
  93.     cout << duration.count() << "\n";
  94.     cin.close();
  95.     cout.close();*/
  96.     return 0;
  97. }
Advertisement
Add Comment
Please, Sign In to add comment