Cod sursa(job #2137344)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 20 februarie 2018 18:59:02
Problema Diamant Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <iostream>
#include <cstdio>
#define NMAX 45005

using namespace std;

int N, M, X, dp[2][NMAX], summax;

void solve()
{
    for(int k = 0; k <= summax; ++k) {
        for(int i = 1; i <= N; ++i) {
            for(int j = 1; j <= M; ++j) {
                if(dp[k % 2][k - i*j] > 0)
                    dp[k % 2][k - i*j] = dp[!(k % 2)][k - i*j] + 1;
                if(dp[k % 2][k + i*j] < summax + 1)
                    dp[k % 2][k + i*j] = dp[!(k % 2)][k + i*j] + 1;
            }
        }
    }
}

int main()
{
    freopen("diamant.in", "r", stdin);
    freopen("diamant.out", "w", stdout);
    scanf("%d %d %d", &N, &M, &X);
    summax = N * (N + 1) * M * (M + 1) / 4;
    solve();
    printf("%d", dp[X % 2][X]);
    return 0;
}