fork(2) download
  1. // Warsaw Rhubarbs
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. int dist(const pair<int,int> & a, const pair<int,int> & b) {
  8. return abs(a.first - b.first) + abs(a.second - b.second);
  9. }
  10.  
  11. struct Ride {
  12. pair<int,int> start, end;
  13. int when_start, when_end;
  14. int id;
  15. void read(int _id) {
  16. id = _id;
  17. cin >> start.first >> start.second >> end.first >> end.second;
  18. cin >> when_start >> when_end;
  19. }
  20. int length() const {
  21. return dist(start, end);
  22. }
  23. };
  24.  
  25. int bonus_start;
  26.  
  27. vector<vector<int>> output;
  28. int super;
  29. struct Car {
  30. pair<int,int> where;
  31. int when;
  32. int id;
  33. int when_can_get(const pair<int,int> & a) const {
  34. return when + dist(where, a);
  35. }
  36. int real_simulate(const Ride & ride, bool indeed) {
  37. ll score = 0;
  38. when += dist(where, ride.start);
  39. if(when <= ride.when_start) {
  40. if(indeed) ++super;
  41. when = ride.when_start;
  42. score += bonus_start;
  43. }
  44. when += ride.length();
  45. if(when <= ride.when_end) {
  46. score += ride.length();
  47. }
  48. else {
  49. assert(!indeed);
  50. score = 0;
  51. }
  52. where = ride.end;
  53. return score;
  54. }
  55. int fake_simulate(const Ride & ride) const {
  56. Car x = *this;
  57. return x.real_simulate(ride, false);
  58. }
  59. int would_wait(const Ride & ride) const {
  60. int get_there = when_can_get(ride.start);
  61. return max(0, ride.when_start - get_there);
  62. }
  63. int would_need(const Ride & ride) const {
  64. return max(when_can_get(ride.start), ride.when_start) - when;
  65. }
  66. void add_ride(const Ride & ride) const {
  67. output[id].push_back(ride.id);
  68. }
  69. };
  70.  
  71.  
  72. int main() {
  73. int h, w, cnt_cars, cnt_rides;
  74. int T;
  75. cin >> h >> w >> cnt_cars >> cnt_rides >> bonus_start >> T;
  76. output.resize(cnt_cars);
  77.  
  78. vector<Ride> rides(cnt_rides);
  79. for(int i = 0; i < cnt_rides; ++i)
  80. rides[i].read(i);
  81.  
  82. vector<Car> cars(cnt_cars);
  83. for(int i = 0; i < cnt_cars; ++i)
  84. cars[i].id = i;
  85.  
  86. vector<bool> done(cnt_rides);
  87.  
  88. int total_score = 0;
  89. int AC = 0;
  90.  
  91. vector<int> far(cnt_rides, INT_MAX);
  92. for(int i = 0; i < cnt_rides; ++i) if(!done[i])
  93. for(int j = 0; j < cnt_rides; ++j) if(i != j) if(!done[j])
  94. far[i] = min(far[i], dist(rides[i].end, rides[j].start));
  95.  
  96. while(true) {
  97. bool anything = false;
  98.  
  99. for(Car & car : cars) {
  100. pair<int, int> best;
  101. best.first = INT_MAX;
  102. for(int i = 0; i < cnt_rides; ++i) if(!done[i]) {
  103. int would_score = car.fake_simulate(rides[i]);
  104. if(would_score == 0) continue; // can't do it in time
  105. int wasted = car.would_need(rides[i]);
  106. int when_would_finish = car.when + wasted + rides[i].length();
  107. if(when_would_finish <= T * 0.98) wasted += far[i] / 15;
  108. best = min(best, {wasted, i});
  109. }
  110. if(best.first == INT_MAX) continue;
  111. int i = best.second;
  112. done[i] = true;
  113. int tmp = car.real_simulate(rides[i], true);
  114. total_score += tmp;
  115. anything = true;
  116. car.add_ride(rides[i]);
  117. ++AC;
  118. }
  119. if(!anything) break;
  120. }
  121. cerr << super << "/" << AC << "/" << cnt_rides << "\n";
  122. cerr << "score = " << total_score / 1e6 << "\n";
  123. for(int i = 0; i < cnt_cars; ++i) {
  124. printf("%d", (int) output[i].size());
  125. for(int x : output[i]) printf(" %d", x);
  126. puts("");
  127. }
  128. }
  129.  
Time limit exceeded #stdin #stdout 5s 8081572KB
stdin
Standard input is empty
stdout
Standard output is empty