Pagini recente » Cod sursa (job #269926) | Cod sursa (job #730304) | Cod sursa (job #2528923) | Cod sursa (job #3218388) | Cod sursa (job #833782)
Cod sursa(job #833782)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 50000;
const int MOD = 10000;
int dp[2][2 * MAXN];
int main()
{
freopen("diamant.in", "r", stdin);
freopen("diamant.out", "w", stdout);
int n, m, x;
scanf("%d %d %d", &n, &m, &x);
int sum = ((n * (n + 1)) / 2) * ((m * (m + 1)) / 2);
if (x > sum || x < -sum) {
printf("0\n");
return 0;
}
int l = 0;
dp[0][sum] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j, l = 1 ^ l) {
for (int s = -sum; s <= sum; ++s) {
dp[1 ^ l][s + sum] = dp[l][s + sum];
if (s + i * j <= sum)
dp[1 ^ l][s + sum] = max(dp[1 ^ l][s + sum],
dp[l][s + sum] + dp[l][s + i * j + sum]);
if (s - i * j >= -sum)
dp[1 ^ l][s + sum] = max(dp[1 ^ l][s + sum],
dp[l][s + sum] + dp[l][s - i * j + sum]);
}
}
printf("%d\n", dp[0][x + sum]);
return 0;
}