Codeforces #609 Div1 B. Domino for Young

本番こっちの方がはるかに簡単に答えている…。
https://codeforces.com/contest/1268/problem/B

問題

ヤング図形が与えられる。
この図形の上に、２マス分の大きさのドミノを敷くことを考える。
最大何個置くことができるか。

解法

図形を白黒市松模様状に塗り分け、少ない方のマス目の数だけドミノを敷ける。

int N;
int A[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll C[2]={};
	FOR(i,N) {
		cin>>A[i];
		
		if(i%2==0) {
			C[0]+=A[i]/2;
			C[1]+=A[i]/2+A[i]%2;
		}
		else {
			C[1]+=A[i]/2;
			C[0]+=A[i]/2+A[i]%2;
		}
	}
	cout<<min(C[0],C[1])<<endl;
	
}

まとめ

見たら本番Aはさんざん苦戦したうえでHackされて、一方こっちは３分でACしてた。