Cod sursa(job #2320865)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 15 ianuarie 2019 11:31:13
Problema Cowfood Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 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 + KMAX + 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]) % 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) {
            ans = ((ans + parity * combinari[k + rest][k]) % MOD + MOD) % MOD;
        }
        return;
    }

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

    state[niv] = 1;
    parity *= -1;
    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) % MOD;

    fout<<ans;

    return 0;
}