Advertisement
Guest User

Untitled

a guest
Feb 21st, 2017
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.29 KB | None | 0 0
  1. #ifdef NOT_DMOJ
  2. //secret header that provides answers to all questions
  3. #include"contest includes.h"
  4. #else
  5. //include everything header for GCC
  6. #include<bits/stdc++.h>
  7. #endif
  8. #pragma region template code
  9. using namespace std;
  10.  
  11. template<typename T>using minheap = priority_queue<T, vector<T>, greater<T>>;
  12.  
  13. template<typename T>using maxheap = priority_queue<T>;
  14. template<typename T>using dpair = pair<T, T>;
  15. typedef long long ll;
  16. typedef dpair<int> pii;
  17. typedef dpair<long long> pll;
  18. typedef dpair<float> pff;
  19. typedef dpair<double> pdd;
  20. template<class T1, class T2>
  21. istream& operator >> (istream &is, pair<T1, T2> &p) {
  22. return is >> p.first >> p.second;
  23. }
  24. template<class T1, class T2>
  25. ostream& operator << (ostream &os, pair<T1, T2> &p) {
  26. return os << "<" << p.first << ", " << p.second << ">";
  27. }
  28. template<class T1, class T2>
  29. void operator+=(vector<T1> &v, const T2 &obj) {
  30. v.push_back(obj);
  31. }
  32. template<class T1>
  33. void operator+=(vector<T1> &v, const T1 &obj) {
  34. v.push_back(obj);
  35. }
  36. const int INF = 0x3f3f3f3f;
  37. const ll mod = 1e9 + 7;
  38. class range {
  39. public:
  40. range(int end) :_start(0), _end(end), _step(1) {}
  41. range(int start, int end) :_start(start), _end(end), _step(1) {}
  42. range(int start, int end, int step) :_start(start), _end(end), _step(step) {}
  43. class iterator {
  44. public: iterator(int v, int s) :val(v), step(s) {};
  45. int operator*() const {
  46. return val;
  47. } int operator++() {
  48. return (val += step);
  49. } bool operator==(const range::iterator &iter) const {
  50. return val == iter.val && step == iter.step;
  51. } bool operator!=(const range::iterator &iter) const {
  52. return !(this->operator==(iter));
  53. } private: int val;
  54. int step;
  55. };
  56. range::iterator begin() {
  57. return{ _start, _step };
  58. }
  59. range::iterator end() {
  60. return{ _end, _step };
  61. }
  62. private:
  63. int _start, _end, _step;
  64. };
  65.  
  66. #pragma endregion
  67.  
  68. const int MAXN = 2005;
  69. ll dp[2][MAXN][MAXN];
  70. vector<pll> possugar;
  71. vector<pll> negsugar;
  72. ll init_energy;
  73. ll sumpos[MAXN];
  74. ll sumneg[MAXN];
  75.  
  76. int main() {
  77. #ifdef NOT_DMOJ
  78. freopen("text.txt", "r", stdin);
  79. #else
  80. cin.tie(0);
  81. cin.sync_with_stdio(0);
  82. #endif
  83. int N;
  84. cin >> N;
  85. for (int a = 0; a < N; a++) {
  86. pll p;
  87. cin >> p;
  88. if (p.first == 0) {
  89. init_energy = p.second;
  90. } else if (p.first > 0) {
  91. possugar.push_back(p);
  92. } else if( p.first < 0){
  93. p.first *= -1;
  94. negsugar.push_back(p);
  95. }
  96. }
  97. possugar.push_back({ 0,init_energy });
  98. negsugar.push_back({ 0,0 });
  99. sort(possugar.begin(), possugar.end());
  100. sort(negsugar.begin(), negsugar.end());
  101. for (int a = 0; a < possugar.size(); a++) {
  102. sumpos[a + 1] = sumpos[a] + possugar[a].second;
  103. }
  104. for (int a = 0; a < negsugar.size(); a++) {
  105. sumneg[a + 1] = sumneg[a] + negsugar[a].second;
  106. }
  107.  
  108. //min distance to
  109. for (int a = 0; a < MAXN; a++) {
  110. for (int b = 0; b < MAXN; b++) {
  111. dp[0][a][b] = 1e15;
  112. dp[1][a][b] = 1e15;
  113. }
  114. }
  115. dp[0][0][0] = dp[1][0][0] = 0;
  116. for (int a = 0; a < possugar.size(); a++) {
  117. for (int b = 0; b < negsugar.size(); b++) {
  118. ll totsugar = sumpos[a + 1] + sumneg[b + 1];
  119.  
  120. //dp[0] pos side
  121. //continue positive
  122. if (a != possugar.size() - 1 &&
  123. totsugar - dp[0][a][b] >= possugar[a + 1].first - possugar[a].first) {
  124.  
  125. dp[0][a + 1][b] = min(dp[0][a + 1][b], dp[0][a][b] +
  126. possugar[a + 1].first - possugar[a].first);
  127. }
  128.  
  129. //go negative side
  130. if (b != negsugar.size() - 1 &&
  131. totsugar - dp[0][a][b] >= possugar[a].first + negsugar[b + 1].first) {
  132.  
  133. dp[1][a][b+1] = min(dp[1][a][b + 1], dp[0][a][b] +
  134. possugar[a].first + negsugar[b + 1].first);
  135. }
  136.  
  137. //dp[1] neg side
  138. //go positive side
  139. if (a != possugar.size() - 1 &&
  140. totsugar - dp[1][a][b] >= possugar[a + 1].first + negsugar[b].first) {
  141.  
  142. dp[0][a + 1][b] = min(dp[0][a + 1][b], dp[1][a][b] +
  143. possugar[a + 1].first + negsugar[b].first);
  144. }
  145. if (b != negsugar.size() - 1 &&
  146. totsugar - dp[1][a][b] >= negsugar[b+1].first - negsugar[b].first) {
  147.  
  148. dp[1][a][b + 1] = min(dp[1][a][b + 1], dp[1][a][b] +
  149. negsugar[b + 1].first - negsugar[b].first);
  150. }
  151. }
  152. }
  153. ll ans = 0;
  154. for (int a = 0; a < possugar.size(); a++) {
  155. for (int b = 0; b < negsugar.size(); b++) {
  156. if (dp[0][a][b] != 1e15 || dp[1][a][b] != 1e15) {
  157. ans = max(ans, sumpos[a + 1] + sumneg[b + 1]);
  158. }
  159. }
  160. }
  161. cout << ans;
  162. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement