Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- struct rock {
- int x, y, z;
- bool accessible;
- int score;
- rock() {
- accessible = false;
- }
- const bool operator<(const rock &other) const {
- if (y != other.y) return y < other.y;
- if (x != other.x) return x < other.x;
- return z < other.z;
- }
- void update(int value) {
- int new_score = z + value;
- if (!accessible) {
- accessible = true;
- score = new_score;
- } else {
- if (new_score > score) {
- score = new_score;
- }
- }
- }
- bool can_come_from(const rock &other, int d_x, int d_y) const {
- return (other.accessible
- && abs(other.x - x) <= d_x
- && abs(other.y - y) <= d_y
- && other.y < y);
- }
- };
- template<typename T, typename U> inline void relaxmax(T &res, const U &x) {
- if (x > res) {
- res = x;
- }
- }
- void solve() {
- int N, H, dX, dY;
- cin >> N >> H >> dY >> dX;
- vector<rock> R(N);
- for (int i = 0; i < N; ++i) {
- cin >> R[i].y >> R[i].x >> R[i].z;
- }
- sort(R.begin(), R.end());
- int64 ret = (int64)100000 * (-N);
- for (int i = 0; i < N; ++i) {
- if (R[i].y <= dY) {
- R[i].update(0);
- }
- for (int j = 0; j < i; ++j) {
- if (R[i].can_come_from(R[j], dX, dY)) {
- R[i].update(R[j].score);
- }
- }
- if (R[i].y + dY >= H) {
- relaxmax(ret, R[i].score);
- }
- }
- cout << ret << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement