kmjp's blog

競技プログラミング参加記です

Codeforces #167 Div1. A. Dima and Staircase

さて、ここからはDiv1本番。何とか解けたけど…。
http://codeforces.com/contest/273/problem/A

問題

2次元空間で、左から右に向かって登っていく階段があり、各段の高さが与えられる。
ここで、多数の箱を落とすことを考える。
箱の幅Wと高さHが与えられ、その箱を左端に落としていく。
各箱を落とした時、その底辺部の高度を答える。

解法

箱は、直前に積まれた箱の高さか、もしくは階段のW段目の高い方に積まれる。
後はこの処理を箱ごとに行うだけ。

int N,M,W,H;
int A[100001];

void solve() {
	int f,r,i,j,k,l, x,y,loop;
	ll LH,CL,hoge;
	
	N=GETi();
	FOR(i,N) A[i]=GETi();
	M=GETi();
	
	LH=A[0];
	FOR(loop,M) {
		W=GETi();
		H=GETi();
		
		hoge=max(LH,(ll)A[W-1]);
		_P("%I64d\n",hoge);
		LH=hoge+H;
	}
	
	return;
}

まとめ

一見問題設定がややこしいけど、意外と簡単な問題。