結果

問題 No.119 旅行のツアーの問題
コンテスト
ユーザー Hachimori
提出日時 2015-01-07 01:40:28
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,793 bytes
コンパイル時間 840 ms
コンパイル使用メモリ 71,092 KB
実行使用メモリ 51,060 KB
最終ジャッジ日時 2024-12-21 10:46:48
合計ジャッジ時間 11,510 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int CITY = 45;


int nCity;
int val[CITY][2];
bool depend[CITY][CITY];

void read() {
    memset(depend, 0, sizeof(depend));
    
    cin >> nCity;
    for (int i = 0; i < nCity; ++i) {
        cin >> val[i][0] >> val[i][1];
    }
    
    int nDepend;
    cin >> nDepend;
    for (int i = 0; i < nDepend; ++i) {
        int s, t;
        cin >> s >> t;
        depend[s][t] = true;
    }
}


vector< pair<int, long long> > getValMaskList(bool former) {
    int maskEnd = former ? (1 << (nCity / 2)) : (1 << ((nCity + 1) / 2));
    int shift   = former ? 0 : nCity / 2;
    int bgn = former ? 0         : nCity / 2;
    int end = former ? nCity / 2 : nCity    ;
    
    vector< pair<int, long long> > ret;
    for (long long mask = 0; mask < maskEnd; ++mask) {
        int sum = 0;
        for (int i = bgn; i < end; ++i) {
            bool needVisit = false;
            for (int j = bgn; j < i; ++j) {
                if (((mask << shift) & (1LL << j)) && depend[j][i]) {
                    needVisit = true;
                    break;
                }
            }
            
            // bit が立ってる
            // → その都市に訪れツアーに参加
            if ((mask << shift) & (1LL << i)) {
                sum += val[i][0];
            }
            // bit が立っておらず、前の都市のツアー履歴から、都市 i のツアーへの参加が必須でない
            // → その都市に訪れツアーに参加しない
            else if (!needVisit) {
                sum += val[i][1];
            }
            // bit が立っておらず、前の都市のツアー履歴から、都市 i のツアーへの参加が必須
            // → その都市を訪れない
            else {
                
            }
        }
        ret.push_back(make_pair(sum, mask << shift));
    }
    
    return ret;
}


void work() {
    if (nCity == 1) {
        cout << max(val[0][0], val[0][1]) << endl;
        return;
    }
    
    // (sum of val, mask)
    // 前半の組み合わせを全列挙
    vector< pair<int, long long> > valMaskList1 = getValMaskList(true);
    
    // (sum of val, mask) 
    // 後半の組み合わせを全列挙
    // ※ただし、前半のツアー参加履歴が考慮されてないため、多めに満足度が計算されている
    vector< pair<int, long long> > valMaskList2 = getValMaskList(false);

    // 満足度の和が大きい順にソート
    sort(valMaskList1.rbegin(), valMaskList1.rend());
    sort(valMaskList2.rbegin(), valMaskList2.rend());

    int ans = 0;
    for (int i = 0; i < valMaskList1.size(); ++i) {
        pair<int, long long> &valMask1 = valMaskList1[i];
        
        for (int j = 0; j < valMaskList2.size(); ++j) {
            pair<int, long long> &valMask2 = valMaskList2[j];
        
            // 満足度の和が大きい順なので、これ以上続けても ans が更新されないので打ち切り
            if (valMask1.first + valMask2.first <= ans) {
                break;
            }
            
            // 後半の都市を訪れたときの満足度の和 (前半のツアー参加履歴を考慮し、正確に計算する)
            int sum = 0;
            
            // どの都市(前半・後半の都市全部合わせて)のツアーに参加したか
            long long mask = valMask1.second | valMask2.second;
            
            for (int ii = nCity / 2; ii < nCity; ++ii) {
                bool needVisit = false;
                for (int jj = 0; jj < ii; ++jj) {
                    if ((mask & (1LL << jj)) && depend[jj][ii]) {
                        needVisit = true;
                        break;
                    }
                }
                
                // bit が立ってる
                // → その都市に訪れツアーに参加
                if (mask & (1LL << ii)) {
                    sum += val[ii][0];
                }
                // bit が立っておらず、前の都市のツアー履歴から、都市 i のツアーへの参加が必須でない
                // → その都市に訪れツアーに参加しない
                else if (!needVisit) {
                    sum += val[ii][1];
                }
                // bit が立っておらず、前の都市のツアー履歴から、都市 i のツアーへの参加が必須
                // → その都市を訪れない
                else {
                    
                }
            }
            
            ans = max(ans, valMask1.first + sum);
        }
    }
    
    cout << ans << endl;
}


int main() {
    read();
    work();
    return 0;
}
0