fork(7) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. struct ticket {
  6. 	int id, validity, price;
  7. };
  8.  
  9. int cutDown(ticket tickets[], int count) {
  10. 	for(int validity = 0; validity <= min(30, count - 1); validity++) {
  11. 		int ticketsCount = 0;
  12. 		for(int i = 0; i < count; i++) {
  13. 			if(tickets[i].validity == validity) {
  14. 				ticketsCount++;
  15. 			}
  16. 		}
  17. 		while(ticketsCount > validity) {
  18. 			int cheapestTicketPosition = -1;
  19. 			int cheapestTicketPrice = 101;
  20. 			for(int i = 0; i < count; i++) {
  21. 				if(tickets[i].validity == validity && tickets[i].price < cheapestTicketPrice) {
  22. 					cheapestTicketPrice = tickets[i].price;
  23. 					cheapestTicketPosition = i;
  24. 				}
  25. 			}
  26. 			tickets[cheapestTicketPosition] = tickets[--count];
  27. 			ticketsCount--;
  28. 		}
  29. 	}
  30. 	return count;
  31. }
  32.  
  33. bool comparator(const ticket t1, const ticket t2) {
  34. 	return t1.id < t2.id;
  35. }
  36.  
  37. int main() {
  38. 	int count;
  39. 	cin >> count;
  40. 	ticket tickets[count];
  41. 	for(int i = 0; i < count; i++) {
  42. 		tickets[i].id = i;
  43. 		cin >> tickets[i].validity >> tickets[i].price;
  44. 	}
  45. 	count = cutDown(tickets, count);
  46. 	sort(tickets, tickets + count, comparator);
  47. 	int maxProfit = 0;
  48. 	do {
  49. 		int profit = 0;
  50. 		for(int i = 0; i < count; i++) {
  51. 			profit += tickets[i].validity > i ? tickets[i].price * (tickets[i].validity - i) : 0;
  52. 		}
  53. 		maxProfit = max(profit, maxProfit);
  54. 	} while(next_permutation(tickets, tickets + count, comparator));
  55. 	cout << maxProfit << endl;
  56. 	return 0;
  57. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
4
1 2
1 4
5 6
7 8
stdout
copy 
1 2
1 4
5 6
7 8

0 8
0 4
0 6
https://ideone.com/cnVnCD
6
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

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!