Cod sursa(job #2595844)

Utilizator alex_benescuAlex Ben alex_benescu Data 8 aprilie 2020 15:22:17
Problema Cowfood Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#define Xp 3210121
using namespace std;
ifstream f("cowfood.in");
ofstream g("cowfood.out");
int n,k,s,i,j,sol,V[32],A[32],dp[32][1<<14],v[22][32];
void Back(int x,int bit){
  if(x==n+1){
    int S=0;
    for(int i=1;i<=k;++i) S+=V[i];
    if(S<=s){
      int M=dp[k][s-S];
      if(bit&1) M=-M;
      sol=(sol+M+Xp)%Xp;
    }
  }
  else{
    Back(x+1,bit);
    int A[k+1];
    for(int i=1;i<=k;++i) A[i]=V[i],V[i]=max(V[i],v[x][i]);
    Back(x+1,bit+1);
    for(int i=1;i<=k;++i) V[i]=A[i];
  }
}
int main(){
  f>>k>>s>>n;
  for(i=1;i<=n;++i)
    for(j=1;j<=k;++j) f>>v[i][j];
  for(i=0;i<=s;++i) dp[0][i]=1;
  for(i=1;i<=k;++i)
    for(j=dp[i][0]=1;j<=s;++j)
      dp[i][j]=(dp[i-1][j]+dp[i][j-1])%Xp;
  Back(1,0);
  g<<(sol-1-s*k+Xp)%Xp;
  return 0;
}