Advertisement
K_Y_M_bl_C

Untitled

Oct 22nd, 2017
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.62 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef vector<int> vi;
  7.  
  8. #define X first
  9. #define Y second
  10. #define mk make_pair
  11. #define inb push_back
  12. #define y1 ggggggggggggg
  13.  
  14. int solve();
  15.  
  16. int main()
  17. {
  18. solve();
  19. return 0;
  20. }
  21.  
  22. const int BUFSZ = (int)1e6 + 7;
  23.  
  24. char buf[BUFSZ];
  25.  
  26. string get_str()
  27. {
  28. scanf(" %s", buf);
  29. return string(buf);
  30. }
  31.  
  32. const double INF = (double)1e9 + 7;
  33.  
  34. int solve()
  35. {
  36. int n;
  37. scanf("%d", &n);
  38. vector<string> a(n);
  39. vector<pair<int, int>> t(n);
  40. set<pair<int, int>> q;
  41. for (int i = 0; i < n; ++i)
  42. {
  43. a[i] = get_str();
  44. int x, x1, y, y1;
  45. scanf("%d.%d %d.%d", &x, &x1, &y, &y1);
  46. t[i].X = x * 100 + x1;
  47. t[i].Y = y * 100 + y1;
  48. //printf("%d %d\n", t[i].X, t[i].Y);
  49. q.insert(mk(t[i].X, i));
  50. }
  51. int ans = INF;
  52. vi anss;
  53. for (int i = 0; i < n; ++i)
  54. {
  55. int cans = t[i].Y;
  56. if (cans > ans)
  57. continue;
  58. q.erase(mk(t[i].X, i));
  59. for (int j = i + 1; j < n; ++j)
  60. {
  61. cans += t[j].Y;
  62. q.erase(mk(t[j].X, j));
  63. if (cans > ans)
  64. continue;
  65. for (int k = j + 1; k < n; ++k)
  66. {
  67. if (k == j)
  68. continue;
  69. cans += t[k].Y;
  70. q.erase(mk(t[k].X, k));
  71. if (cans > ans)
  72. continue;
  73. pair<double, int> kek = *q.begin();
  74. cans += kek.X;
  75. if (cans < ans)
  76. ans = cans, anss = { kek.Y, i, j, k };
  77. cans -= t[k].Y;
  78. cans -= kek.X;
  79. q.insert(mk(t[k].X, k));
  80. }
  81. q.insert(mk(t[j].X, j));
  82. cans -= t[j].Y;
  83. }
  84. q.insert(mk(t[i].X, i));
  85. cans -= t[i].Y;
  86. }
  87. printf("%d.", ans / 100);
  88. if (ans % 100 < 10)
  89. printf("0");
  90. printf("%d\n", ans % 100);
  91. for (int i = 0; i < anss.size(); ++i)
  92. {
  93. for (char c : a[anss[i]])
  94. printf("%c", c);
  95. puts("");
  96. }
  97. return 0;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement