Cod sursa(job #2611705)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 7 mai 2020 14:34:13
Problema Cowfood Scor 18
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>

using namespace std;

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

const int MOD = 3210121, NMax = 20, KMax = 30, SMax = 10000;

int V[NMax + 5], N, K, S, A[NMax + 5][KMax + 5], DP[SMax + 5][KMax + 5], Maxi[NMax + 5][KMax + 5], Sol;
bool Use[NMax + 5];

int Stars_and_Bars(int stars, int bars = K)
{
    if(stars < 1)
        return 0;

    return DP[stars - 1][bars - 1];
}

int Shrink(int x)
{
    if(x >= MOD)
        x -= MOD;

    return x;
}

void Process(int len, int Sum)
{
    if(len & 1)
        Sol = Shrink(Sol + Stars_and_Bars(S - Sum + K));
    else
        Sol = Shrink(Sol + MOD - Stars_and_Bars(S - Sum + K));
}

void BKT(int pos)
{
    for(int i = V[pos - 1] + 1; i <= N; i++)
    {
        if(Use[i]) continue;

        V[pos] = i;
        Use[i] = true;
        int Sum = 0;

        for(int k = 1; k <= K; k++)
        {
            Maxi[pos][k] = max(Maxi[pos - 1][k], A[i][k]);
            Sum += Maxi[pos][k];
        }
        Process(pos, Sum);

        if(pos < N)
           BKT(pos + 1);

        Use[i] = false;
    }
}

void Precalc()
{
    for(int i = 0; i <= S; i++)
        DP[i][0] = 1;

    for(int i = 1; i <= S; i++)
        for(int j = 1; j <= K; j++)
            DP[i][j] = Shrink(DP[i - 1][j] + DP[i - 1][j - 1]);

    for(int i = 1; i <= S; i++)
        for(int j = 0; j <= K; j++)
            DP[i][j] = Shrink(DP[i - 1][j] + DP[i][j]);
}

int main()
{
    fin >> K >> S >> N;

    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= K; j++)
            fin >> A[i][j];

    Precalc();
    BKT(1);

    fout << Stars_and_Bars(S) - Sol << '\n';

    fin.close();
    fout.close();

    return 0;
}