CF302に参加。Dで典型的なミスをやらかしてレート微減。
http://codeforces.com/contest/543/problem/A
解法
典型的なDP。
dp[人][残り作成行数][残り許容バグ数]=組み合わせ数、としてDPを行うとO(NMB)に収まる。
DPはdp[i][m][b]=dp[i-1][m][b]+dp[i][m-1][b-A[i]]で更新していくだけ。
int N,M,B; ll V; int A[1010],Z; ll dp[510][510]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>B>>V; FOR(i,N) cin>>A[i]; int m,b; dp[M][B]=1; FOR(i,N) { for(m=M;m>=1;m--) { for(b=B;b>=A[i];b--) if(dp[m][b]) { dp[m-1][b-A[i]] += dp[m][b]; if(dp[m-1][b-A[i]]>=V) dp[m-1][b-A[i]]-=V; } } } ll ret=0; FOR(b,B+1) ret+=dp[0][b]; cout<<ret%V<<endl; }
まとめ
O(NM^2B)の人がいることを期待したけど、pretestが強くてそこは皆対策済みであり、Hackは狙えなかった。