Advertisement
Guest User

Untitled

a guest
Sep 3rd, 2015
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1.  
  2. struct rock {
  3.     int x, y, z;
  4.     bool accessible;
  5.     int score;
  6.     rock() {
  7.         accessible = false;
  8.     }
  9.     const bool operator<(const rock &other) const {
  10.         if (y != other.y) return y < other.y;
  11.         if (x != other.x) return x < other.x;
  12.         return z < other.z;
  13.     }
  14.     void update(int value) {
  15.         int new_score = z + value;
  16.         if (!accessible) {
  17.             accessible = true;
  18.             score = new_score;
  19.         } else {
  20.             if (new_score > score) {
  21.                 score = new_score;
  22.             }
  23.         }
  24.     }
  25.     bool can_come_from(const rock &other, int d_x, int d_y) const {
  26.         return (other.accessible
  27.             && abs(other.x - x) <= d_x
  28.             && abs(other.y - y) <= d_y
  29.             && other.y < y);
  30.     }
  31. };
  32.  
  33. template<typename T, typename U> inline void relaxmax(T &res, const U &x) {
  34.     if (x > res) {
  35.         res = x;
  36.     }
  37. }
  38.  
  39. void solve() {
  40.     int N, H, dX, dY;
  41.     cin >> N >> H >> dY >> dX;
  42.     vector<rock> R(N);
  43.     for (int i = 0; i < N; ++i) {
  44.         cin >> R[i].y >> R[i].x >> R[i].z;
  45.     }
  46.     sort(R.begin(), R.end());
  47.    
  48.     int64 ret = (int64)100000 * (-N);
  49.    
  50.     for (int i = 0; i < N; ++i) {
  51.         if (R[i].y <= dY) {
  52.             R[i].update(0);
  53.         }
  54.         for (int j = 0; j < i; ++j) {
  55.             if (R[i].can_come_from(R[j], dX, dY)) {
  56.                 R[i].update(R[j].score);
  57.             }          
  58.         }
  59.         if (R[i].y + dY >= H) {
  60.             relaxmax(ret, R[i].score);
  61.         }
  62.     }
  63.    
  64.     cout << ret << endl;
  65.  
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement