Cod sursa(job #2638886)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 30 iulie 2020 14:27:26
Problema Cowfood Scor 76
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <bits/stdc++.h>

using namespace std;

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

const int mod = 3210121;
int k, s, n, v[50][50], dp[50][30004], stiva[50], maxx[50][50];
long long total, total2;


int bkt(int index){
    if (index > 1){
        int sum = 0;
        for (int i = 1; i <= k; ++i){
            maxx[index - 1][i] = max(maxx[index - 2][i], v[stiva[index - 1]][i]);
            sum += maxx[index - 1][i];
        }
        int ans = dp[k][s - sum];
        if ((index - 1) % 2 == 1){
            total2 += ans;
            total2 %= mod;
        }
        else{
            total2 -= ans;
            if (total2 < 0) total2 += mod;
        }
    }
    for (int i = stiva[index - 1] + 1; i <= n; ++i){
        stiva[index] = i;
        bkt(index + 1);
    }
}

int main(){
    fin >> k >> s >> n;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= k; ++j)
        {
            fin >> v[i][j];
            maxx[0][j] = -1;
        }
    }
    for (int i = 0; i <= 30000; ++i){
        dp[0][i] = 1;
    }
    for (int i = 1; i <= k; ++i){
        for (int j = 0; j <= 30000; ++j){
            dp[i][j] = dp[i - 1][j];
            if (j > 0){
                dp[i][j] = (1LL * dp[i][j] + dp[i][j - 1]) % mod;
            }
        }
    }
    total = (dp[k][s] - (1LL * s * k) % mod +  mod) % mod;
    total -= 1;
    if (total < 0) total += mod;
    bkt(1);
    fout << (total - total2 + mod) % mod;
    fin.close();
    fout.close();
    return 0;
}