Cod sursa(job #2638882)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 30 iulie 2020 14:20:35
Problema Cowfood Scor 12
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cowfood.in");
ofstream fout("cowfood.out");
const int mod = 3210121;
int n, s, k, v[55][55], total_valide, dp[55][10006], total_esuate, stiva[55], maxx[55][55];
int solve(int index, int sum){
    if (dp[index][sum] > 0){
        return dp[index][sum];
    }
    if (sum < 0){
        return 0;
    }
    if (index == 0){
        return 1;
    }
    return dp[index][sum] = (1LL * solve(index, sum - 1) + solve(index - 1, sum)) % mod;
}
void bkt(int index){
    if (index > 1){
        int j = stiva[index - 1], sum = 0;
        for (int i = 1; i <= k; ++i){
            maxx[index - 1][i] = max(maxx[index - 2][i], v[j][i]);
            sum += maxx[index - 1][i];
        }
        sum = dp[k][s - sum];
        if ((index - 1) % 2 == 1){
            total_esuate  = (total_esuate + sum) % mod;
        }
        else{
            total_esuate = (total_esuate - sum + mod) % mod;
        }
    }
    for (int i = stiva[index - 1] + 1; i <= n; ++i){
        stiva[index] = i;
        bkt(index + 1);
    }
}
int main(){
    fin >> n >> s >> k;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= k; ++j){
            fin >> v[i][j];
        }
    }
    total_valide = (solve(k, s) - (s * k) % mod + mod) % mod;
    total_valide = (total_valide - 1 + mod) % mod;
    bkt(1);
    fout << (total_valide - total_esuate + mod) % mod;
    return 0;
}