Cod sursa(job #833782)

Utilizator sebii_cSebastian Claici sebii_c Data 13 decembrie 2012 01:24:04
Problema Diamant Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#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;
}