結果

問題 No.107 モンスター
コンテスト
ユーザー なお
提出日時 2014-12-19 00:38:55
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,598 bytes
コンパイル時間 1,473 ms
コンパイル使用メモリ 165,572 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-12 01:28:15
合計ジャッジ時間 2,336 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 12 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
const int MOD = 1000000007;

vector<int> P,M;
unsigned int up, um;

inline void bits(unsigned int &p, int n){ p |= (1<<n); }
inline void bitu(unsigned int &p, int n){ p &= ~(1<<n); }
inline bool biti(unsigned int p, int n){ return !!(p & (1<<n)); };
inline int  bitc(unsigned int p){int c=0;for(;p;p&=p-1) c++; return c; }

int dpm(int v){
    vector<pair<int,int> > listM;
    listM.push_back(make_pair(0,0));
    REP(i,M.size()){
        if(biti(um, i)) continue;
        int size = listM.size();
        REP(j,size){
            auto &v = listM[j];
            listM.push_back(make_pair(v.first + M[i], v.second|(1<<i)));
        }
    }
    for(auto it = listM.rbegin(); it != listM.rend(); ++it){
        if(it->first < v) return it->second;
    }
    return 0;
}

int dpp(int v){
    vector<pair<int,int> > listP;
    listP.push_back(make_pair(0,0));
    REP(i,P.size()){
        if(biti(up, i)) continue;
        int size = listP.size();
        REP(j,size){
            auto &v = listP[j];
            listP.push_back(make_pair(v.first + P[i], v.second|(1<<i)));
        }
    }
    for(auto it = listP.rbegin(); it != listP.rend(); ++it){
        if(it->first <= v) return it->second;
    }
    return 0;
}

int D[20];
int main(){
    int N;
    cin >> N;
    REP(i,N) cin >> D[i];
    int pn = 0, mn = 0;

    REP(i,N){
        if(D[i] < 0){
            M.push_back(-D[i]);
        } else {
            P.push_back(D[i]);
        }
    }

    int mv = 100, v = 100, cnt = 1000;

    while(cnt--){
        int b = dpm(v);
        if(b){
            REP(i,M.size()){
                if(biti(b,i)){
                    bits(um, i);
                    v -= M[i], mv += 100;
                }
            }
        } else {
            b = dpp(mv-v);
            if(b){
                REP(i,P.size()){
                    if(biti(b,i)){
                        bits(up, i);
                        v += P[i];
                    }
                }
            } else {
                int idx = -1, j = 1<<29;
                REP(i,P.size()){
                    if(biti(up,i)) continue;
                    if(j > P[i]){
                        j = P[i], idx = i;
                    }
                }
                if(idx >= 0){
                    bits(up, idx);
                    v += P[idx];
                    if(v > mv) v = mv;
                }
            }
        }
    }
    if(um != (1<<M.size())-1) v = 0;

    cout << v << endl;
    return 0;
}
0