Submission #2668613

---

Source Code Expand

#include <iostream>
#include <climits>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <limits>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
 
using namespace std;
typedef long long ll;
 
 
typedef pair<ll,ll> P;
long long int INF = 1e18;
double Pi = 3.141592653589;
const int mod = 1000000007;
// memset(a,0,sizeof(a)); →全部０にする
 
vector<int> G[100005];
std::vector<P> tree[100010];
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
 
#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define re(i,a,b) for(i=a;i<=b;i++)
 
ll i,j,ii,jj;
ll n,m,ans=0,sum;
ll x,y,k;
ll a[100005];
ll hidari,migi,mid;
bool dp[5105][5105];
int dd[5100];
 
 
 
bool solve(ll x){
	if(dd[x]==2){
		return true;
	}else if(dd[x]==1){
		return false;
	}
    //x番目を除いたらどうなるか
    for(i=0;i<n+2;i++){
        for(j=0;j<k+2;j++){
            dp[i][j]=false;
        }
    }
    ll z=1;
	dp[0][0]=true;
    for(i=0;i<n;i++){
        if(i==x)continue;
        for(j=0;j<k;j++){
            if(dp[z-1][j] && j+a[i]<=k)dp[z][j+a[i]]=true;
            if(dp[z-1][j])dp[z][j]=true;
        }
        z++;
    }
	bool flag=false;
	y = max(0ll,k-a[x]);
    for(j=y;j<k;j++){
        if(j>=0 && dp[n-1][j])flag=true;
    }
	if(flag){
		dd[x] = 2;
		return true;//必要
	}else{
		dd[x] = 1;
		return false;//不必要
	}
}
 
 // huhitu huhitu huhitu huhitu hitu hitu って並ぶ
 // 1 1 1 1 2 2 2 2 2
int main(){
    cin>>n>>k;
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    hidari=0;
    migi=n-1;
    while(migi-hidari>50){
        mid=(migi+hidari)/2;
        if(solve(mid)){
            migi=mid;
        }else{
            hidari=mid;
        }
    }
	/*for(int i=0;i<n;i++){
		if(solve(i)){
			pe(i);p("は必要");
		}else{
			pe(i);p("は不必要");
		}
	}*/
    for(ii=hidari-100;ii<=hidari+100;ii++){
        if(ii<0 || ii>=n)continue;
        if(!solve(ii)){
			ans=ii;
		}else{
			ans = ii-1;
			break;
		}
        
    }
	p(ans+1);
    return 0;
}

Submission Info

Judge Result