Submission #1178014

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
typedef long long int ll;
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define EREP(i,n) for (int i=1;i<=(n);i++)
//#define EVEL 1

#ifndef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {X;}
#define TF(f) {f;}
#define END {}
#endif
const int MOD = 1000000007;
const int INF = 1000000;
#define NMAX 5000
#define MAX 10

    ll sum[NMAX+1],temp,buff=0;
    int N,K,ans=0;
    int A[100010];
    int count=0;
    bool dp[NMAX+10][NMAX+10],dp1[NMAX+10][NMAX+10];
    bool vis[NMAX+10][NMAX+10],vis1[NMAX+10][NMAX+10];
        int low=0,high,mid;

bool dfs(ll x,ll y){
    //    DEB(x)DEB(y)END
    if(y<0)return false;
    if(vis[x][y]){
        return dp[x][y];
    }else vis[x][y]=true;
    if(y==0){dp[x][y]=true; /*DEB(dp[x][y])DEB(x)DEB(y)END*/ return dp[x][y];}
    if(x==N){dp[x][y]=false;/*DEB(dp[x][y])DEB(x)DEB(y)END*/ return dp[x][y];}

        if(dfs(x+1,y)||dfs(x+1,y-A[x])){
            dp[x][y]=true;
        }else dp[x][y]=false;
        //DEB(dp[x][y])DEB(x)DEB(y)END
    return dp[x][y];
}
bool front(ll x,ll y){
    if(y<0)return false;
    if(x<0){
        //DEB(dp1[x][y])DEB(x)DEB(y)END
        return false;
     }
    if(vis1[x][y]){
        return dp1[x][y];
    }else vis1[x][y]=true;
    if(y==0){
        dp1[x][y]=true; //DEB(dp1[x][y])DEB(x)DEB(y)END
        return dp1[x][y];
    }


        if(front(x-1,y)||front(x-1,y-A[x])){
            dp1[x][y]=true;
        }else dp1[x][y]=false;
        //DEB(dp1[x][y])DEB(x)DEB(y)END
    return dp1[x][y];
}


int main(){
    ios_base::sync_with_stdio(false);
    cin>>N>>K;
    ans=N;
    REP(i,N){cin>>A[i];}
    sort(A,A+N);
    high=N-1;
    REP(i,N){
        bool m=false;
        FOR(j,0,K+1){
            if(j<0)j=0;
            //if(front(i,j)) m=true;
            FOR(k,K-A[i]-j,K+1){
                //if(j+k>K)break;
                DEB(i)DEB(j)DEB(k)
                TF(front(i,j))
                TF(dfs(i,k))
                TF(dfs(i,k)&&front(i,j))
                END
                if(dfs(i,k)&&front(i,j)){
                    ans=i;
                    if(i==N-1)ans=0;
                    m=true;
                    break;
                }

            }
            if(m)break;
        }
        if(m)break;
    }

    cout<<ans<<endl;
}
//ABC056 AtCoDeer

Submission Info

Judge Result