結果

問題 No.334 門松ゲーム
ユーザー rapurasu
提出日時 2016-09-05 17:46:16
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 2,325 bytes
コンパイル時間 1,767 ms
コンパイル使用メモリ 160,820 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-15 20:28:56
合計ジャッジ時間 1,960 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

 #include<bits/stdc++.h>
 using namespace std;
#define INF 1000000000
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
int N;
int K[13];
bool dp[1<<14];
//消すことが可能か
bool check(long long x){
     REP(i,N){
         REP(j,i){
             REP(k,j){
                 if(!(x>>i&1)){
                    if(!(x>>j&1)){
                       if(!(x>>k&1)){
                          if((K[i]<K[j]&&K[j]>K[k])||(K[i]>K[j]&&K[j]<K[k])){
                              return true;
                          }
                       }
                    }
                 }
             }
         }
     }
     return false;
}

void bit_dp(){
     long long x=(1<<N)-1;
     int a=-1;
     int b=-1;
     int c=-1;
     dp[x]=false;
     for(long long i=x-1;i>=0;i--){
         if(check(i)==false){
            dp[i]=false;
         }else{
            dp[i]=false;
            for(int l=0;l<N;l++){
                for(int j=l+1;j<N;j++){
                    for(int k=j+1;k<N;k++){

                       if(!((i>>l)&1)){
                          if(!((i>>j)&1)){
                             if(!((i>>k)&1)){
                                long long y=i;
                                y=y|(1<<l);
                                y=y|(1<<j);
                                y=y|(1<<k);
                                if((dp[y]==false)&&((K[l]<K[j]&&K[j]>K[k])||(K[l]>K[j]&&K[j]<K[k]))){
                                   dp[i]=true;
                                   if(i==0){
                                      if(a==-1){
                                         a=l;
                                         b=j;
                                         c=k;
                                         //cout<<i<<"a"<<y<<endl;
                                      }
                                   }
                                }
                                
                                //dp[i]=true;
                             }
                          }
                       }
                    }
                }
            }
            
         }
         //cout<<i<<" "<<dp[i]<<endl;
     }
     if(a==-1){
        cout<<-1<<endl;
     }else{
        cout<<a<<" "<<b<<" "<<c<<endl;
     }
}

int main(){
    cin>>N;
    REP(i,N){
       cin>>K[i];
    }
    bit_dp();
}
0