Advertisement
Guest User

Untitled

a guest
Nov 18th, 2019
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.27 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. // CCO '16 P2 - Splitting Hares
  3.  
  4. #define EPS 1e-7
  5.  
  6. using namespace std;
  7.  
  8. int x[4005],y[4005],w[4005];
  9. vector<int> l,r;
  10. int cur;
  11.  
  12. inline double slope(int i1,int i2) {
  13. return ((double) (y[i1] - y[i2])) / (x[i1] - x[i2]);
  14. }
  15.  
  16. bool cmp(int i1,int i2) {
  17. return slope(i1,cur) < slope(i2,cur);
  18. }
  19.  
  20. inline bool eq(double d1,double d2) {
  21. return (abs(d1 - d2) < EPS);
  22. }
  23.  
  24. int main() {
  25. int N,i,j,k,sum1,sum2,ans,dec1,dec2,temp;
  26. double nxt;
  27.  
  28. scanf("%d",&N);
  29.  
  30. for (i = 0;i < N;i++)
  31. scanf("%d%d%d",&x[i],&y[i],&w[i]);
  32.  
  33. ans = 0;
  34. for (i = 0;i < N;i++) {
  35. sum1 = 0;
  36. sum2 = 0;
  37. dec1 = 0;
  38. dec2 = 0;
  39. l.clear();
  40. r.clear();
  41.  
  42. for (j = 0;j < N;j++) {
  43. if (x[j] == x[i]) {
  44. sum1 += w[j];
  45. sum2 += w[j];
  46.  
  47. if (y[j] > y[i])
  48. dec1 += w[j];
  49. else if (y[j] < y[i])
  50. dec2 += w[j];
  51. }
  52. else if (x[j] > x[i]) {
  53. r.push_back(j);
  54. sum2 += w[j];
  55. }
  56. else {
  57. l.push_back(j);
  58. sum1 += w[j];
  59. }
  60. }
  61.  
  62. cur = i;
  63. sort(l.begin(),l.end(),cmp);
  64. sort(r.begin(),r.end(),cmp);
  65.  
  66. j = 0;
  67. k = 0;
  68. while (j < l.size() || k < r.size()) {
  69. temp = max(max(dec1,dec2) + max(w[i],0),dec1 + dec2 + w[i]);
  70. ans = max(ans,max(temp,0) + max(sum1,sum2) - dec1 - dec2 - w[i]);
  71.  
  72. if (j == l.size())
  73. nxt = slope(r[k],i);
  74. else if (k == r.size())
  75. nxt = slope(l[j],i);
  76. else
  77. nxt = min(slope(l[j],i),slope(r[k],i));
  78.  
  79. sum1 -= dec1;
  80. sum2 -= dec2;
  81. dec1 = 0;
  82. dec2 = 0;
  83.  
  84. while (j < l.size() && eq(slope(l[j],i),nxt)) {
  85. sum2 += w[l[j]];
  86. dec1 += w[l[j]];
  87. j++;
  88. }
  89.  
  90. while (k < r.size() && eq(slope(r[k],i),nxt)) {
  91. sum1 += w[r[k]];
  92. dec2 += w[r[k]];
  93. k++;
  94. }
  95. }
  96. }
  97.  
  98. printf("%d\n",ans);
  99.  
  100. return 0;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement