結果

提出番号	2056
提出者	dohatsutsu
言語	C++
提出日時	2018-08-04 15:07:18
問題名	(66)Cut onion
結果	WA
点数	0%

---

テストケース

ソースコード

#include<bits/stdc++.h>
using namespace std;
int N,K,B;
int A[16];

int limit;
bool dfs(int x,int c,int t[16],int sz,int cost){
  if(cost>limit)return false;
  if(x==N)return true;

  if( A[x] <= 0 )return dfs(x+1,c,t,sz,cost);
  
  int tmp[16];
  for(int i=0;i<sz;i++)tmp[i]=t[i];
  
  for(int i=0;i<sz;i++){
    int u=t[i];
    A[x] -= u;
    swap(t[i],t[sz-1]);
    if( dfs(x,c,t,sz-1,cost) )return true;
    A[x] += u;

    for(int j=0;j<sz;j++)t[j]=tmp[j];
      
    if(t[i]>A[x]){
      t[i]-=A[x];
      if( dfs(x+1,c,t,sz,cost+1) )return true;
      t[i]+=A[x];
    }
  }
  
  if(c>0){
    if( dfs(x+1, c-1,t,sz,cost) )return true;
    t[sz]=B-A[x];
    if( dfs(x+1, c-1,t,sz+1,cost+1) )return true;
  }

  return false;
}

int main(){
  cin>>N>>K>>B;
  for(int i=0;i<N;i++)cin>>A[i];
  int t[16];
  
  for( limit = 0; limit < 15-K ; limit ++){
    if( dfs(0,K,t,0,0) ){
      cout<<limit<<endl;
      return 0;
    }
  }
  
  cout<<15-K<<endl;
  return 0;
}