Ekiben

2 secs 1024 MB

dyktr_06

問題

提出

テストケース

解説

この問題は、半分全列挙というテクニックを使うことによって正解することができます。

具体的には、駅弁を $0$ から $2$ 個買ったときのカロリーの組み合わせを全探索した配列 $P$ と、 $0$ から $3$ 個買ったときのカロリーの組み合わせを全探索した配列 $Q$ をそれぞれ計算しておきます。

$P$ の要素数を $n$ とすると、それぞれの $i \: (1 \leq i \leq n)$ について、配列 $Q$ の中で、 $K - P_i$ を超えない最大の値を二分探索で求めることによって最大で摂取するカロリーを求めることができます。

計算量は、ソートがボトルネックとなるため $O(N^3 \log N^3)$ となり、十分高速です。
( $P$ について二分探索を行うと $O(N^3 \log N^2)$ となります。)

実装例(C++)

#include <bits/stdc++.h>

using namespace std;

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

    vector<long long> p, q;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            p.push_back(a[i] + a[j]);
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                q.push_back(a[i] + a[j] + a[k]);
            }
        }
    }
    sort(q.begin(), q.end());
    long long ans = 0;
    for(auto x : p){
        auto iter = upper_bound(q.begin(), q.end(), k - x);
        if(iter == q.begin()) continue;
        iter--;
        ans = max(ans, x + *iter);
    }
    cout << ans << endl;
}