fork download
copy 
  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
comments (?)
stdin
copy 
4
1 1
2 2
3 3
4 4
stdout
copy 
9
https://ideone.com/2JAXnv
e-olymp 7254
language:
C++ (gcc 8.3)
created:
3 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!