Cod sursa(job #1219097)

Utilizator MaarcellKurt Godel Maarcell Data 13 august 2014 14:01:14
Problema Diamant Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <iostream>
#define XMAX 80200
using namespace std;


int N,M,X,sum, a[25][25][XMAX*4];

int main(){
    ifstream in("diamant.in");
    ofstream out("diamant.out");
    in >> N >> M >> X;

    sum = N*M*(N*M+1)/2;
    if (X>sum || X<-sum){
        out << 0;
        return 0;
    }

    a[1][1][XMAX]=a[1][1][XMAX+1]=a[1][1][XMAX-1]=1;

    int i,j,k;
    for (j=2; j<=M; j++)
        for (k=-sum; k<=sum; k++){
            a[1][j][XMAX+k]=a[1][j-1][XMAX+k];
            a[1][j][XMAX+k]+=a[1][j-1][XMAX+k-j];
            a[1][j][XMAX+k]+=a[1][j-1][XMAX+k+j];
    }

    for (i=2; i<=N; i++)
        for (j=1; j<=M; j++)
            for (k=-sum; k<=sum; k++){
                if (j==1){
                    a[i][j][XMAX+k]=a[i-1][M][XMAX+k];
                    a[i][j][XMAX+k]+=a[i-1][M][XMAX+k-i];
                    a[i][j][XMAX+k]+=a[i-1][M][XMAX+k+i];
                }
                else{
                    a[i][j][XMAX+k]=a[i][j-1][XMAX+k];
                    a[i][j][XMAX+k]+=a[i][j-1][XMAX+k-i*j];
                    a[i][j][XMAX+k]+=a[i][j-1][XMAX+k+i*j];
                }
            }

    out << a[N][M][XMAX+X];
    return 0;
}