Source Code

 Problem:         User: sdfzyhy

 Memory: 1416K        Time: 32MS

 Language: G++        Result: Accepted

     Source Code

     //POJ 1000

     #include<cmath>

     #include<queue>

     #include<vector>

     #include<string>

     #include<cstdio>

     #include<cstring>

     #include<cstdlib>

     #include<iostream>

     #include<algorithm>

     #define rep(i,n) for(int i=0;i<n;++i)

     #define F(i,j,n) for(int i=j;i<=n;++i)

     #define D(i,j,n) for(int i=j;i>=n;--i)

     using namespace std;

     int getint(){

         int r=,c=; char ch=getchar();

         for(;!isdigit(ch);ch=getchar()) if (ch=='-') c=-;

         for(;isdigit(ch);ch=getchar()) r=r*+ch-'';

         return r*c;

     }

     const int N=,INF=~0u>>;

     const double eps=1e-;

     /******************template***********************/

     #define debug

     int n,m,a[];

     bool vis[][],dp[][];

     bool f(int x,int y){

         if (vis[x][y]) return dp[x][y];

         vis[x][y]=;

         if (y==) return dp[x][y]=;

         if (y<=a[x]+) return dp[x][y]=;

         int next;

         if (x==n*) next=;

         else next=x+;

         F(i,,a[x]) if (f(next,y-i)==) return dp[x][y]=;

         return dp[x][y]=;

     }

     int main(){

     #ifndef ONLINE_JUDGE

         freopen("input.txt","r",stdin);

         freopen("output.txt","w",stdout);

     #endif

         while(scanf("%d",&n)!=EOF && n){

             m=getint();

             F(i,,n<<) a[i]=getint();

             memset(vis,,sizeof vis);

             memset(dp,,sizeof (dp));

             printf("%d\n",f(,m));

     //        F(i,1,n<<1) F(j,1,m) printf("f(%d,%d)=%d\n",i,j,dp[i][j]);

         }

         return ;

     }