AtCoder Beginner Contest 056

Submission #1179968

Source codeソースコード

        #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(){
            scanf("%d%d",&N,&K);
            ans=N;
            REP(i,N){scanf("%d",&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;
                            m=true;
                            break;
                        }
                    }
                    if(m)break;
                }
                if(m)break;
            }
            cout<<ans<<endl;
        }

Submission

Task問題 D - No Need
User nameユーザ名 Nafmo
Created time投稿日時
Language言語 C++14 (Clang 3.8.0)
Status状態 TLE
Score得点 300
Source lengthソースコード長 3491 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Compiler messageコンパイルメッセージ

./Main.cpp:92:29: warning: expression result unused [-Wunused-value]
DEB(i)DEB(j)DEB(k)
^
./Main.cpp:22:25: note: expanded from macro 'DEB'
#define DEB(X) {X;}
^
./Main.cpp:92:35: warning: expression result unused [-Wunused-value]
DEB(i)DEB(j)DEB(k)
^
./Main.cpp:22:25: note: expanded from macro 'DEB'
#define DEB(X) {X;}
^
./Main.cpp:92:41: warning: expression result unused [-Wunused-value]
DEB(i)DEB(j)DEB(k)
^
./Main.cpp:22:25: note: expanded from macro 'DEB'
#define DEB(X) {X;}
^
3 warnings generated.

Test case

Set

Set name Score得点 / Max score Cases
Sample - 0_000.txt,0_001.txt,0_002.txt
Subtask 300 / 300 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 / 300 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
0_000.txt AC 3 ms 6400 KB
0_001.txt AC 2 ms 6400 KB
0_002.txt AC 2 ms 6400 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 4 ms 6528 KB
1_007.txt AC 2 ms 6400 KB
1_008.txt AC 4 ms 11904 KB
1_009.txt AC 9 ms 16128 KB
1_010.txt AC 3 ms 4480 KB
1_011.txt AC 2 ms 4352 KB
1_012.txt AC 2 ms 4352 KB
1_013.txt AC 2 ms 4352 KB
1_014.txt AC 2 ms 4352 KB
1_015.txt AC 4 ms 11776 KB
1_016.txt AC 3 ms 6400 KB
1_017.txt AC 2 ms 6400 KB
1_018.txt AC 3 ms 6400 KB
1_019.txt AC 6 ms 11904 KB
1_020.txt AC 4 ms 11904 KB
1_021.txt AC 4 ms 11776 KB
1_022.txt AC 3 ms 7168 KB
1_023.txt AC 3 ms 6912 KB
1_024.txt AC 6 ms 11904 KB
1_025.txt AC 7 ms 11904 KB
2_026.txt AC 2 ms 4352 KB
2_027.txt AC 14 ms 6528 KB
2_028.txt AC 2 ms 6528 KB
2_029.txt AC 185 ms 53120 KB
2_030.txt AC 897 ms 98560 KB
2_031.txt AC 2 ms 4352 KB
2_032.txt AC 2 ms 4352 KB
2_033.txt AC 2 ms 4352 KB
2_034.txt AC 2 ms 4352 KB
2_035.txt AC 3 ms 4352 KB
2_036.txt AC 12 ms 52992 KB
2_037.txt AC 174 ms 6528 KB
2_038.txt AC 2 ms 6528 KB
2_039.txt AC 175 ms 6528 KB
2_040.txt TLE
2_041.txt AC 12 ms 52992 KB
2_042.txt AC 12 ms 52992 KB
2_043.txt AC 23 ms 36608 KB
2_044.txt AC 12 ms 48896 KB
2_045.txt AC 26 ms 44800 KB
2_046.txt AC 396 ms 77952 KB
2_047.txt AC 672 ms 77952 KB
2_048.txt AC 930 ms 77952 KB
2_049.txt AC 974 ms 69888 KB
2_050.txt AC 979 ms 69760 KB