Aizu Online Judge 0529 - Darts

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0529

日本語なので.

解法

ダーツを使わないことを点数0を得ることと考えれば, 半分全列挙でとけます.

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> pi;
vector<int> comb;

int main() {
    int N, M;
    while (cin >> N >> M, N | M) {
        pi = vector<int>(N + 1);
        comb = vector<int>((N + 1) * (N + 1));
        for (int i = 0; i < N; i++) {
            cin >> pi[i];
        }
        pi[N] = 0;

        for (int i = 0; i < N + 1; i++) {
            for (int j = 0; j < N + 1; j++) {
                comb[i * (N + 1) + j] = pi[i] + pi[j];
            }
        }
        sort(comb.begin(), comb.end());

        int ans = 0;
        for (int i = 0; i < N + 1; i++) {
            for (int j = 0; j < N + 1; j++) {
                int fscore = pi[i] + pi[j];
                if (fscore <= M) {
                    int idx = lower_bound(comb.begin(), comb.end(), M - fscore) - comb.begin(), lscore;
                    if (idx >= comb.size() || comb[idx] != M - fscore) lscore = comb[idx - 1];
                    else lscore = comb[idx];
                    ans = max(ans, fscore + lscore);
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}

感想

時間かかりすぎですが, 解けてよかったです.