JOI2013春合宿day3 コアラ

問題

日本語なので本文参照（http://imoz.jp/data/joi/2013-sp-d3-koala.pdf）

方針

dp[i] := i番目の家にコアラがいるときの、体力の最大値
とするようなDPをしたい。
これは更新にO(n)かかるので、全体の計算量はO(n^2)になって間に合わない。

が、mod毎に見ればただのdpになる。
なので、mod毎の最良値をsegment木でもっておけば、普通にDPできる。
segment treeに入れるのは、dp[i] + x[i] / d * a
（距離がdふえるごとにコストはa減るので）

更新のときは、今のmodがmだとすると、
前のmodが0〜m-1のときは、1回だけ余計にジャンプが必要で、
modがm以上のときはそのままx[i] / d - x[j] / d回のが必要回数。
なので0〜m-1とm以上の二つの部分にわけてsegment treeをから値を調べればいい。

本番のコードでは、なんかスライド最小値的なことをやらなければならないのかなー
とか思って余計なことをしていたが、デックに入る値は一つだけなのでぜんぜん意味なかった。
通れば正義。

ソースコード

ll k, m, d, a, n, s, t;
ll q[100010];
ll dp[100010], x[100010], gain[100010];
vi mods;
 
template<class T>struct SegTree{
	T *dat, *num;
	int n;
	SegTree(int size = 1000000){
		for(n = 1; n < size; n *= 2);
		dat = new T[2 * n - 1];
		num = new T[n];
		init();
	}
	~SegTree(){ delete dat; }
	
	void init(){
		rep(i, n) num[i] = -infll, dat[i + n - 1] = i;
		for(int i = n - 2; i >= 0; i--){
			if(num[dat[i * 2 + 1]] >= num[dat[i * 2 + 2]]) dat[i] = dat[i * 2 + 1];
			else dat[i] = dat[i * 2 + 2];
		}
	}
	void update(int k, T a){
		num[k] = a;
		k += n - 1;
		
		while(k > 0){
			k = (k - 1) / 2;
			if(num[dat[k * 2 + 1]] >= num[dat[k * 2 + 2]]) dat[k] = dat[k * 2 + 1];
			else dat[k] = dat[k * 2 + 2];
		}
	}
	T query(int a, int b, int k, int l, int r){
		if(r <= a || b <= l) return -inf;
		if(a <= l && r <= b) return dat[k];
		
		int li = query(a, b, k * 2 + 1, l, (l + r) / 2);
		int ri = query(a, b, k * 2 + 2, (l + r) / 2, r);
		
		if(li != -inf && ri != -inf) return num[li] >= num[ri] ? li : ri;
		return li != -inf ? li : ri;
	}
};
 
int main(){
	cin >> k >> m >> d >> a >> n;
	rep(i, n + 10) dp[i] = -infll;
	dp[0] = 0;
	x[0] = k;
	for(int i = 1; i <= n; i++){
		cin >> x[i] >> gain[i];
		mods.pb(x[i] % d);
	}
	mods.pb(k % d);
	sort(all(mods));
	mods.erase(unique(all(mods)), mods.end());
	
	ll ans = -((m - k + d - 1) / d) * a;
	int M = mods.size();
	vector<deque<ll> > q(M);
	SegTree<ll> seg(M);
	int kk = lower_bound(all(mods), k % d) - mods.begin();
	q[kk].pb(k / d * a);
	seg.update(kk, k / d * a);
	
	for(int i = 1; i <= n; i++){
		int mod = x[i] % d;
		mod = lower_bound(all(mods), mod) - mods.begin();
		
		int i1 = seg.query(0, mod, 0, 0, seg.n);
		if(i1 != -inf && q[i1].size()){
			assert(0 <= i1 && i1 < mod);
			dp[i] = max(dp[i], q[i1].front() - x[i] / d * a - a + gain[i]);
		}
		int i2 = seg.query(mod, seg.n, 0, 0, seg.n);
		if(i2 != -inf && q[i2].size()){
			assert(mod <= i2 && i2 < mods.size());
			dp[i] = max(dp[i], q[i2].front() - x[i] / d * a + gain[i]);
		}
		ans = max(ans, dp[i] - (m - x[i] + d - 1) / d * a);
		
		while(q[mod].size() && q[mod].back() <= dp[i] + x[i] / d * a) q[mod].pop_back();
		q[mod].pb(dp[i] + x[i] / d * a);
		seg.update(mod, q[mod].front());
	}
	cout << ans << endl;
	
	return 0;
}