### tahsin_protik's blog

By tahsin_protik, history, 6 weeks ago,

Hello, Codeforces community.

It is my pleasure to invite you all to the replay contest of Intra RUET Junior Contest (Round 1), which took place two days back with the beginner contestants of Rajshahi University of Engineering & Technology. The contest will follow the format of regular ICPC contests.

The contest will be suitable for beginners (ie. Codeforces Div3 contestants) but we invite you all to participate for fun. :D

Start time: 19:15(+6GMT) 10/08/2020

Duration: 3 hours

Number of Problems: 7

The contest platform is toph.co, you can register for the contest here.

The problems of the contest were reviewed, authored and tested by shefin.cse16, I_love_ProParThinkNot, Hasnaine_, tanus_era, wan-_-s, Shajib_, Hasinur_, tahsin_protik, A_Modern_Desperado, joynahiid, JOYTUN_17, Complexity_Cutter, Salam_35, Emama.emu

We look forward to your participation and hope that you enjoy the problem set, best of luck in the contest.

•  » » 6 weeks ago, # ^ |   +8 I also used suffix and prefix dp . Code#include using namespace std; int lft_dp[101][10001]; int rgt_dp[101][10001]; int n,m; int a[101],b[101],ok[101]; int solve(int pos,int sum) { if(sum<0)return 0; if(pos>n) { if(sum==0)return 1; else return 0; } int &ret=rgt_dp[pos][sum]; if(ret!=(-1))return ret; ret=0; if(solve(pos+1,sum-a[pos]))ret=1; if(solve(pos+1,sum-b[pos]))ret=1; return ret; } int sol(int pos,int sum) { if(sum<0)return 0; if(pos<1) { if(sum==0)return 1; else return 0; } int &ret=lft_dp[pos][sum]; if(ret!=(-1))return ret; ret=0; if(sol(pos-1,sum-a[pos]))ret=1; if(sol(pos-1,sum-b[pos]))ret=1; return ret; } void s() { memset(rgt_dp,-1,sizeof rgt_dp); memset(lft_dp,-1,sizeof lft_dp); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); } solve(1,m); sol(n,m); int pos=-1,dan,bam; for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) { int rgt=j; int lft=m-j; if(sol(i-1,lft) && solve(i+1,rgt)) { pos=i; bam=lft; dan=rgt; break; } } } if(pos==-1) { printf("NO\n");return ; } printf("YES\n"); for(int i=pos-1;i>=1;i--) { if(sol(i-1,bam-a[i])) { bam=bam-a[i]; ok[i]=1; } else { bam=bam-b[i]; ok[i]=2; } } ok[pos]=0; for(int i=pos+1;i<=n;i++) { if(solve(i+1,dan-a[i])) { dan=dan-a[i]; ok[i]=1; } else { dan=dan-b[i]; ok[i]=2; } } for(int i=1;i<=n;i++) { if(i!=n)printf("%d ",ok[i]); else printf("%d\n",ok[i]); } } main() { int t; scanf("%d",&t); while(t--)s(); }