Cod sursa(job #2397949)

Utilizator RazvanPanaiteRazvan Panaite RazvanPanaite Data 4 aprilie 2019 21:56:57
Problema Diamant Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <bits/stdc++.h>
#define DMAX 44110
#define MOD 10000

using namespace std;

ifstream fin("diamant.in");
ofstream fout("diamant.out");

int dp[2][2*DMAX];
int n,m,x,maxim,acm,prec;

inline void swapp(int& x,int& y){
    int aux=x;
    x=y;
    y=aux;
}

int main(){
    int i,j,k,val;
    fin>>n>>m>>x;
    maxim=n*(n+1)/2*m*(m+1)/2;
    if(x>maxim || x+maxim<0){
        fout<<0<<'\n';
        return 0;
    }
    acm=1;
    dp[prec][DMAX]=dp[prec][DMAX+1]=dp[prec][DMAX-1]=1;

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++){
            if(i==1 && j==1)
               continue;
            val=i*j;
            for(k=-maxim;k<=maxim;k++)
                dp[acm][k+DMAX]=0;

            for(k=-maxim;k<=maxim;k++){
                if(dp[prec][k+DMAX])
                   {dp[acm][k+DMAX]+=dp[prec][k+DMAX];
                    dp[acm][k+DMAX]%=MOD;
                   }
                if(k+val<=maxim)
                   {dp[acm][k+val+DMAX]+=dp[prec][k+DMAX];
                    dp[acm][k+val+DMAX]%=MOD;
                   }
                if(k-val>=-maxim)
                   {dp[acm][k-val+DMAX]+=dp[prec][k+DMAX];
                    dp[acm][k-val+DMAX]%=MOD;
                   }
            }
            swapp(acm,prec);
        }
    fout<<dp[prec][x+DMAX]<<'\n';
}