結果

問題 No.818 Dinner time
コンテスト
ユーザー yuriko32
提出日時 2025-06-21 22:48:02
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
RE  
実行時間 -
コード長 1,692 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,826 ms
コンパイル使用メモリ 200,624 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-21 22:48:09
合計ジャッジ時間 6,961 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 RE * 1
other AC * 8 RE * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 10;
const int MAX_M = 10;
const int INF = 1e9;


int N, M;
vector<int> A(MAX_N + 1), B(MAX_N + 1);


vector<vector<int>> dp(MAX_M + 1, vector<int>(1 << MAX_N, -INF));


bool check_bit(int mask, int pos) {
    return (mask >> pos) & 1;
}


int clear_bit(int mask, int pos) {
    return mask & ~(1 << pos);
}

int solve(int day, int mask) {
    
    if (day == M) return 0;
    
    
    if (dp[day][mask] != -INF) return dp[day][mask];
    
    int res = -INF;

    for (int K = 1; K <= N; K++) {
        
        vector<int> choices;
        for (int j = 0; j < K; j++) {
            if (check_bit(mask, j)) {
                choices.push_back(j + 1); 
            }
        }
        
        int sz = choices.size();
        for (int subset = 0; subset < (1 << sz); subset++) {
            int score = 0;
            int new_mask = mask;
            for (int i = 0; i < sz; i++) {
                int chicken = choices[i];
                if ((subset >> i) & 1) {
                    score += B[chicken];
                    new_mask = clear_bit(new_mask, chicken - 1);
                } else{
                    score += A[chicken];
                }
            }
            res = max(res, score + solve(day + 1, new_mask));
        }
    }
    
    return dp[day][mask] = res;
}

int main() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
        cin >> B[i];
    }

    
    for (int i = 0; i <= M; i++) {
        for (int j = 0; j < (1 << N); j++) {
            dp[i][j] = -INF;
        }
    }
    
    int result = solve(0, (1 << N) - 1);
    cout << result << endl;
    
    return 0;
}
0