Submission #1178172


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(y==0){return true;}
    if(vis[x][y]){
        return dp[x][y];
    }else vis[x][y]=true;
    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
        if(x==-1&&y==0)return true;
        else 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(k<0)k=0;
                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+1,k)&&front(i-1,j)){
                    ans=i;
                    if(i==0)ans++;
                    if(i==N-1)ans=0;
                    m=true;
                    break;
                }
            }
            if(m)break;
        }
        if(m)break;
    }
    cout<<ans<<endl;
}

Submission Info

Submission Time
Task D - No Need
User Nafmo2
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2710 Byte
Status WA
Exec Time 2103 ms
Memory 98816 KB

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 0 / 300 0 / 300
Status
AC × 3
AC × 13
WA × 13
AC × 22
WA × 28
TLE × 1
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt
Subtask 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 2_026.txt, 2_027.txt, 2_028.txt, 2_029.txt, 2_030.txt, 2_031.txt, 2_032.txt, 2_033.txt, 2_034.txt, 2_035.txt, 2_036.txt, 2_037.txt, 2_038.txt, 2_039.txt, 2_040.txt, 2_041.txt, 2_042.txt, 2_043.txt, 2_044.txt, 2_045.txt, 2_046.txt, 2_047.txt, 2_048.txt, 2_049.txt, 2_050.txt
Case Name Status Exec Time Memory
0_000.txt AC 3 ms 8448 KB
0_001.txt AC 3 ms 8448 KB
0_002.txt AC 3 ms 8448 KB
1_003.txt AC 2 ms 4352 KB
1_004.txt AC 2 ms 4352 KB
1_005.txt AC 2 ms 4352 KB
1_006.txt AC 5 ms 10496 KB
1_007.txt WA 3 ms 10496 KB
1_008.txt WA 4 ms 12544 KB
1_009.txt AC 10 ms 16384 KB
1_010.txt WA 2 ms 4352 KB
1_011.txt WA 2 ms 4352 KB
1_012.txt WA 2 ms 4352 KB
1_013.txt WA 2 ms 4352 KB
1_014.txt WA 2 ms 4352 KB
1_015.txt WA 4 ms 12544 KB
1_016.txt AC 4 ms 8448 KB
1_017.txt WA 3 ms 8448 KB
1_018.txt AC 4 ms 8448 KB
1_019.txt AC 6 ms 12544 KB
1_020.txt WA 4 ms 12544 KB
1_021.txt WA 4 ms 12544 KB
1_022.txt WA 4 ms 12544 KB
1_023.txt WA 4 ms 12544 KB
1_024.txt AC 6 ms 15488 KB
1_025.txt AC 8 ms 15488 KB
2_026.txt AC 2 ms 4352 KB
2_027.txt WA 18 ms 10624 KB
2_028.txt WA 3 ms 10496 KB
2_029.txt WA 170 ms 53760 KB
2_030.txt AC 972 ms 98816 KB
2_031.txt WA 2 ms 4352 KB
2_032.txt WA 3 ms 4352 KB
2_033.txt WA 2 ms 4352 KB
2_034.txt WA 2 ms 4352 KB
2_035.txt WA 3 ms 4352 KB
2_036.txt WA 12 ms 53760 KB
2_037.txt AC 213 ms 10624 KB
2_038.txt WA 3 ms 10496 KB
2_039.txt AC 214 ms 10624 KB
2_040.txt TLE 2103 ms 53760 KB
2_041.txt WA 12 ms 53760 KB
2_042.txt WA 12 ms 53760 KB
2_043.txt WA 23 ms 41344 KB
2_044.txt WA 12 ms 53760 KB
2_045.txt WA 27 ms 49664 KB
2_046.txt AC 404 ms 78336 KB
2_047.txt AC 702 ms 80384 KB
2_048.txt AC 1019 ms 78336 KB
2_049.txt AC 998 ms 74240 KB
2_050.txt AC 1026 ms 70144 KB