Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <fstream>
- #include <vector>
- #include <cmath>
- using namespace std;
- bool check(vector<pair<double, int>> vec, int l, double current_time) {
- vector<pair<double, int>> first_vec = vec;
- vector<pair<double, int>> second_vec = vec;
- bool started = false;
- double first_s = 0;
- double second_s = 0;
- while (first_vec.size() && second_vec.size()) {
- if (started) {
- if (first_vec[0].first < second_vec[0].first) {
- first_s += first_vec[0].first * first_vec[0].second;
- second_s += first_vec[0].first * second_vec[0].second;
- second_vec[0].first -= first_vec[0].first;
- first_vec.erase(first_vec.begin());
- if (first_s - second_s < l) {
- return false;
- }
- } else {
- first_s += second_vec[0].first * first_vec[0].second;
- second_s += second_vec[0].first * second_vec[0].second;
- first_vec[0].first -= second_vec[0].first;
- second_vec.erase(second_vec.begin());
- if (first_s - second_s < l) {
- return false;
- }
- }
- } else {
- if (first_vec[0].first < current_time) {
- first_s += first_vec[0].first * first_vec[0].second;
- current_time -= first_vec[0].first;
- first_vec.erase(first_vec.begin());
- } else {
- first_s += current_time * first_vec[0].second;
- first_vec[0].first -= current_time;
- started = true;
- current_time = 0;
- if (first_s - second_s < l) {
- return false;
- }
- }
- }
- }
- return first_s - second_s >= l;
- }
- inline double round(double number) {
- return floor(number * 1000 + 0.5) / 1000;
- }
- int main(int argc, char **argv) {
- ifstream fin("trains.in");
- int l, n;
- double max_time = 0;
- fin >> l >> n;
- vector<pair<double, int>> vec(n);
- for (int i = 0; i < n; i++) {
- fin >> vec[i].first >> vec[i].second;
- max_time += vec[i].first;
- }
- fin.close();
- double lower_bound = 0;
- double upper_bound = max_time;
- double current_time;
- double previous = current_time;
- while (round(upper_bound - lower_bound) != 0) {
- current_time = lower_bound + (upper_bound - lower_bound) / 2;
- if (check(vec, l, current_time)) {
- upper_bound = current_time;
- } else {
- lower_bound = current_time;
- }
- previous = current_time;
- }
- ofstream fout("trains.out");
- fout << round(current_time);
- fout.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement