WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #186 Div2 C "Ilya and Matrix"

問題

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

イリヤはとても気立てのよいライオンだ。彼は数学が好きである。数学のオブジェクトの中で、彼がすきなのは行列である。今、彼は複雑な行列の問題を解かなければならない。

2^n * 2^nサイズの正方形の行列と4^nの整数がある。これらの数を行列に(1つのセルに1つの数を)配置し、そして結果としてできた行列の美しさを最大化する必要がある。

2^n * 2^nサイズの行列の美しさは、下記のアルゴリズムから得られる整数である。

1. 行列の要素から最大の数を見つける。それをmとしよう。
2. もしn = 0であれば、行列の美しさはmと等しい。
   そうでなければ、行列は4つの2^(n-1) * 2^(n-1)サイズの
   サブ行列にわけることができる。
   そして、行列の美しさはmと4つのサブ行列の美しさの総和と等しい

このアルゴリズムは再帰的に適用される。

イリヤを助けるため、課題を解決し、行列の美しさ最大値を出力せよ。

制約

1 <= 4^n <= 2 * 10^6
1 <= 配置する数の値 <= 10^9



考えた事

つまりだ、足せる数が4分の1ずつ減ってくってことだ。

ソートして、合計値出して、インデックスを4分の1に減らしてって総和をだせばよい。


ソースコード

typedef long long I64;

I64 a[2000050];

int main() {
    int n;
    cin >> n;
    for( int i = 0; i < n; i++ ){
        cin >> a[i+1];
    }

    // 降順にソート
    sort( a + 1, a + n + 1, greater<I64>() ); 

    // 最初からの総和を出す
    for( int i = 2; i <= n; i++ ){
        a[i] += a[i-1];
    }

    // インデックスを4分の1にしてって総和をだす
    I64 ans = 0;
    while( n > 0 ){
        ans += a[n];
        n /= 4;
    }

    cout << ans << endl;
}