Cod sursa(job #1995357)

Utilizator DjokValeriu Motroi Djok Data 27 iunie 2017 20:56:41
Problema Diamant Scor 30
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Semestrul 2 Marime 0.86 kb
#include <bits/stdc++.h>
using namespace std;

const int N = 90005;
const int MAGIC = N / 2;
const int MOD = 1e4;

int i, j, n, m, sum, a[405], nr, row; 
long long need;
map<int, int> dp[405];

int DP(int poz, int val) {
  if(val < 0 || val >= N) return 0;
  if(dp[poz].count(val)) return dp[poz][val];
  if(poz < 1) return 0;

  dp[poz][val] += DP(poz - 1, val - a[poz]);
  dp[poz][val] += DP(poz - 1, val);
  dp[poz][val] += DP(poz - 1, val + a[poz]);

  return dp[poz][val];
}

int main() {
  ifstream cin("diamant.in");
  ofstream cout("diamant.out");
  ios_base::sync_with_stdio(0);

  cin >> n >> m >> need;

  for(i = 1; i <= n; ++i)
    for(j = 1; j <= m; ++j)
      a[++nr] = i * j, sum += a[nr];

  if(need > sum || need < -sum) return cout << "0\n", 0;

  dp[0][MAGIC] = 1;

  cout << DP(nr, MAGIC + need) << '\n';

  return 0;
}