fork download
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <climits>
  5. using namespace std;
  6.  
  7. //Структура для представления одного отрезка
  8. struct Line {
  9. int price;
  10. int length;
  11. };
  12.  
  13. //Функция сортировщик по цене в порядке возрастания
  14. bool comparator_price (Line i, Line j) {
  15. return i.price < j.price;
  16. }
  17.  
  18. int main() {
  19. int n, price, length, cheapest = INT_MAX;
  20. cin >> n;
  21. Line lines_by_price[n];
  22.  
  23. for (int i = 0; i < n; i++) {
  24. Line l;
  25. cin >> length >> price;
  26. l.price = price;
  27. l.length = length;
  28. lines_by_price[i] = l;
  29. }
  30.  
  31. //Сортируем все отрезки по цене, чтобы была возможность "отсечь"
  32. //слишком дорогие отрезки, когда цена одного(или двух) будет
  33. //больше текущей минимальной
  34. sort(&lines_by_price[0], &lines_by_price[n], comparator_price);
  35.  
  36. for (int i = 0; i < n; i++) {
  37. Line first_side = lines_by_price[i];
  38. if (first_side.price > cheapest) break;
  39. vector<Line> sides = {};
  40. //Перебираем все возможные тройки отрезков, отсекая
  41. //слишком дорогие, основываясь на сортировке по цене
  42. //и текущей минимальной цене
  43. for (int j = 0; j < n; j++) {
  44. if (lines_by_price[j].price != first_side.price && lines_by_price[j].length <= first_side.length) {
  45. sides.push_back(lines_by_price[j]);
  46. Line second_side = lines_by_price[j];
  47. if (first_side.price + second_side.price > cheapest) break;
  48. for (auto third_side: sides) {
  49. if ((third_side.length != second_side.length && third_side.price != second_side.price)
  50. && first_side.length < second_side.length + third_side.length
  51. && second_side.length < first_side.length + third_side.length
  52. && third_side.length < second_side.length + first_side.length) {
  53. if (first_side.price + second_side.price + third_side.price < cheapest) {
  54. cheapest = first_side.price + second_side.price + third_side.price;
  55. }
  56. break;
  57. }
  58. }
  59. }
  60. }
  61. }
  62. //Если ни одна тройка отрезков не подошла, значит составить
  63. //треугольник невозможно - выводим "-1"
  64. if (cheapest == INT_MAX) cheapest = -1;
  65. cout << cheapest;
  66. return 0;
  67. }
Success #stdin #stdout 0s 4668KB
stdin
4
1 1
2 2
3 3
4 4
stdout
9