結果

問題 No.818 Dinner time
ユーザー ninhtay
提出日時 2025-06-21 22:52:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,344 bytes
コンパイル時間 775 ms
コンパイル使用メモリ 81,372 KB
実行使用メモリ 27,300 KB
最終ジャッジ日時 2025-06-21 22:53:04
合計ジャッジ時間 4,939 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 TLE * 1
other -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int N, D;
vector<int> A, B;
int max_score = 0;

void dfs(int day, vector<bool> used, int score) {
    if (day == D) {
        max_score = max(max_score, score);
        return;
    }

    for (int L = 1; L <= N; ++L) {
        // Lấy danh sách gà còn sống từ 1 đến L
        vector<int> alive;
        for (int i = 0; i < L; ++i) {
            if (!used[i]) alive.push_back(i);
        }

        int K = alive.size();
        // Thử mọi cách chọn: 2^K tổ hợp trứng/thịt
        for (int mask = 0; mask < (1 << K); ++mask) {
            vector<bool> new_used = used;
            int gain = 0;
            for (int i = 0; i < K; ++i) {
                int g = alive[i];
                if ((mask >> i) & 1) {
                    // Làm thịt
                    gain += B[g];
                    new_used[g] = true;
                } else {
                    // Đẻ trứng
                    gain += A[g];
                }
            }
            dfs(day + 1, new_used, score + gain);
        }
    }
}

int main() {
    cin >> N >> D;
    A.resize(N);
    B.resize(N);
    for (int i = 0; i < N; ++i) {cin >> A[i]>>B[i];}

    vector<bool> used(N, false);
    dfs(0, used, 0);

    cout << max_score << endl;
    return 0;
}
0