fork(6) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wzBByv
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!