# Cod sursa(job #2308414)

Utilizator Data 27 decembrie 2018 00:55:14 Cowfood 30 cpp-64 done Arhiva de probleme 1.52 kb
``````#include <bits/stdc++.h>

const int SMAX=10000, KMAX =30, NMAX = 20, MOD=3210121;

using namespace std;

ifstream fin("cowfood.in");
ofstream fout("cowfood.out");

int combinari[SMAX + 1][KMAX + 1], experiments[NMAX + 1][KMAX + 1];

int k,s,n;

void calcComb()
{
combinari[0][0]=1;
for(int i = 1; i <= s + k; i++)
{
combinari[i][0]=1;
for(int j = 1; j <= k && j <= i; j++)
{
combinari[i][j] = combinari[i - 1][j] + combinari[i - 1][j - 1];
combinari[i][j] %= MOD;
}
}
}

int state[NMAX + 1];
int maxVals[NMAX + 1][KMAX + 1];
int ans;
int parity = 1;

void back(int niv)
{
if(niv==n+1)
{
int suma_maxime=0;
for(int i = 0; i < k; i++)
suma_maxime+=maxVals[n][i];

int rest=s-suma_maxime;
if(rest<0)
{
return ;
}
ans=(ans+parity*combinari[k+rest][k]+MOD)%MOD;

return;
}
state[niv]=0;
for(int i=0;i<k;++i)
{
maxVals[niv][i]=maxVals[niv-1][i];
}
back(niv + 1);
state[niv]=1;
parity*=-1;
for(int i=0;i<k;++i)
{
maxVals[niv][i]=max(maxVals[niv-1][i],experiments[niv-1][i]);
}
back(niv + 1);
parity*=-1;
}

int main()
{
fin >> k >> s >> n;
calcComb();
for(int i = 0; i < n; i++)
{
for(int j = 0; j < k; j++)
fin>>experiments[i][j];
}

for(int i = 0; i < k; i++)
maxVals[0][i] = 0;

back(1);

ans = ( ans - (s * k + 1) + MOD) % MOD;

fout<<ans;

return 0;
}``````