fork(7) download
  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
stdin
4
1 2
1 4
5 6
7 8
stdout
1 2
1 4
5 6
7 8

0 8
0 4
0 6