Codeforces #186, C : Ilya and Matrix

問題文

http://codeforces.com/contest/313/problem/C

概要

個の整数が与えられ、それを の行列上に配置する。
行列の "美しさ" を次のように定義したとき、美しさが最大になるように配置した場合の美しさを求めよ。

1. 行列に含まれる最大の要素を m とする
2. 行列のサイズがによって分岐します　
   • 行列のサイズが なら m を美しさとする
   • それ以外のとき、行列を四等分し、それらの美しさと m の和を美しさとする

解法

各分割の段階に於いて、美しさに足される数字の数は、1, 4, 16, ...　と増えていきます。
実際の配置がどうなるかは無視して結果だけ求めればよいので、各数字が足される回数にのみ着目します。
最適な配置に於いては、大きな数字ほど多くの回数足されることになります。
従って、数字を予め降順ソートしておいて、先頭 個を足す処理を繰り返すと答えが得られます。

コード

typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	vector<LL> ary( n );
	FOR( a, ary )
	{
		cin >> a;
	}
	sort( ALL( ary ), greater<LL>() );
	
	vector<LL> csum( 1, 0 );
	partial_sum( ALL( ary ), back_inserter( csum ) );

	VI pows( 1, 1 );
	while ( pows.back() < n )
	{
		pows.PB( pows.back() * 4 );
	}

	LL res = 0;
	REP( i, 0, pows.size() )
	{
		res += csum[ pows[i] ];
	}

	cout << res << endl;

	return 0;
}