我出过的东方系列题目 » ZOJ3227

ZOJ3227
ZOJ3227.cpp


#include <map>
#include <cstdio>
#include <utility>
#include <cassert>
#include <algorithm>

using namespace std;

#define L(p) ((p) << 1)
#define R(p) (((p) << 1) ^ 1)

const int inf = 1000000000;

struct SegmentTree {
	int m;
	int a[65536];

	void init(int n, int d) {
		m = 1;
		while (m < n) {
			m <<= 1;
		}
		for (int i = 0; i < n; ++i) {
			a[m + i] = i * d;
		}
		for (int i = n; i < m; ++i) {
			a[m + i] = -inf;
		}
		for (int i = m - 1; i > 0; --i) {
			a[i] = max(a[L(i)], a[R(i)]);
		}
	}

	void set(int i, int v) {
		i += m;
		do {
			a[i] = v;
			v = max(v, a[i ^ 1]);
			i >>= 1;
		} while (i > 0);
	}

	int get(int p, int pl, int pr, int l, int r) {
		if (pl == l && pr == r) {
			return a[p];
		} else {
			int pm = (pl + pr) / 2;
			if (r <= pm) {
				return get(L(p), pl, pm, l, r);
			} else if (pm <= l) {
				return get(R(p), pm, pr, l, r);
			} else {
				return max(
						get(L(p), pl, pm, l, pm),
						get(R(p), pm, pr, pm, r));
			}
		}
	}

	int get(int l, int r) {
		// l = max(0, l);
		// r = min(m, r);
		return get(1, 0, m, l, r);
	}
};

SegmentTree lst, rst;
pair<pair<int, int>, int> v[65536];

int main() {
	int w, s, n, a, b, c;

	while (scanf("%d%d%d%d%d%d", &w, &s, &n, &a, &b, &c) != EOF) {
		assert(1 <= w && w <= 30000);	// 1 <= w <= 30000
		assert(1 <= s && s <= 900000000);	// 1 <= s <= 900000000
		assert(0 <= n && n <= 60000);	// 0 <= n <= 60000
		assert(0 <= a && a <= 10);	// 0 <= a <= 10
		assert(0 <= b && b <= 100000000);	// 0 <= b <= 100000000
		assert(0 <= c && c <= 1000000000);	// 0 <= c <= 1000000000
		for (int i = 0; i < n; ++i) {
			assert(scanf("%d%d%d", &v[i].first.second, &v[i].first.first, &v[i].second) == 3);
			assert(0 <= v[i].first.second && v[i].first.second < w);// 0 <= x < w
			assert(0 <= v[i].first.first && v[i].first.first < s);	// 0 <= y < s
			assert(-10000 < v[i].second && v[i].second < 10000 && v[i].second != 0);	// 0 < |z| < 10000
		}
		sort(v, v + n);
		for (int i = 1; i < n; ++i) {
			assert(v[i].first != v[i - 1].first);	// if i != j, then (x_i, y_i) != (x_j, y_j)
		}
		lst.init(w, +a);
		rst.init(w, -a);

		int p = 0;
		while (p < n) {
			map<int, int> mp;
			int y = v[p].first.first;
			while (p < n && v[p].first.first == y) {
				int x = v[p].first.second;
				int z = v[p].second;
				if (z != 0) {
					mp[x] = z;
					if (z < 0) {
						if (x - 1 >= 0) {
							mp[x - 1];
						}
						if (x + 1 < w) {
							mp[x + 1];
						}
					}
				}
				++p;
			}
			for (map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it) {
				it->second += max(
						lst.get(0, it->first + 1) - a * it->first,
						rst.get(it->first, w) + a * it->first);
			}
			for (map<int, int>::const_iterator it = mp.begin(); it != mp.end(); ++it) {
				lst.set(it->first, it->second + a * it->first);
				rst.set(it->first, it->second - a * it->first);
			}
		}

		int ans = -inf;
		for (int i = 0; i < w; ++i) {
			ans = max(ans, lst.a[lst.m + i] - a * i);
			ans = max(ans, rst.a[rst.m + i] + a * i);
		}
		ans += b + c;
		printf("%d\n", ans);
	}

	return 0;
}
Leave a Reply