Cod sursa(job #2114617)

Utilizator robx12lnLinca Robert robx12ln Data 25 ianuarie 2018 18:11:04
Problema Diamant Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("diamant.in");
ofstream fout("diamant.out");
int D[88205], N, M, X, v[405], K, MAX, f[88205];
int main(){
    fin >> N >> M >> X;
    for( int i = 1; i <= N; i++ )
        for( int j = 1; j <= M; j++ )
            v[++K] = i * j;
    MAX = N * (N + 1) * M * (M + 1) / 4;
    D[MAX] = 1;
    for( int i = 1; i <= K; i++ ){
        for( int j = MAX; j >= - MAX; j-- )
            if( D[j + MAX] != 0 && j + v[i] <= MAX )
                D[ j + MAX + v[i] ] += D[j + MAX], f[ j + MAX + v[i] ] = 1;
        for( int j = -MAX; j <= MAX; j++ )
            if( D[j + MAX] != 0 && j - v[i] >= -MAX && f[j + MAX] == 0 )
                D[ j + MAX - v[i] ] += D[j + MAX];
        memset( f, 0, sizeof(f) );
    }
    fout << D[X + MAX] << "\n";
    return 0;
}