Cod sursa(job #2439308)

Utilizator PetyAlexandru Peticaru Pety Data 15 iulie 2019 17:10:43
Problema Cowfood Scor 28
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<bits/stdc++.h>
using namespace std;

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

const int mod = 3210121;

int k, s, n, c[10052][32], v[22][32], ans, st[22], maxa[32][32], sum[100002];

void backt (int x) {
  if (x > 0) {
    for (int i = 1; i <= k; i++)
      maxa[x][i] = max(maxa[x - 1][i], v[st[x]][i]);
    int S = 0;
    for (int i = 1; i <= k; i++)
      S += maxa[x][i];
    if (S <= s) {
      if (x % 2 == 1)
        ans = (ans - sum[s - S] + mod) % mod;
      else
        ans = (ans + sum[s - S]) % mod;
    }
  }
  if (x < n) {
    for (int i = st[x] + 1; i <= n; i++) {
      st[x + 1] = i;
      backt(x + 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];
  c[0][0] = 1;
  for (int i = 1; i <= s + k - 1; i++) {
    c[i][0] = c[i][i] = 1;
    for (int j = 1; j <= min(i - 1, k - 1); j++)
      c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
  }
  sum[0] = 1;
  for (int i = 1; i <= s; i++)
    sum[i] = (sum[i - 1] + c[i + k - 1][k - 1]) % mod;
  ans = (sum[s] - (s * k + 1) % mod + mod) % mod;
  backt(0);
  fout << ans << "\n";
	return 0;
}