Cod sursa(job #2137370)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 20 februarie 2018 19:15:02
Problema Diamant Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <iostream>
#include <cstdio>
using namespace std;
int n,m,x,cnt,v[405];
int dp[2][50005];
int main()
{
    freopen("diamant.in","r",stdin);
    freopen("diamant.out","w",stdout);
    scanf("%d%d%d",&n,&m,&x);

    int idx=0,id=0,ids=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            {
                v[++idx]=i*j;
                dp[0][i*j]++;
            }

    }
    dp[0][0]=1;
    for(int i=1;i<=((m+1)*m)/2*((n+1)*n)/2;i++)
        {
            int ok=0;
            for(int j=1;j<=m*n;j++)
            {
                if(ok==0&&i==v[j])
                {
                    ok=1;
                    continue;
                }
                if(dp[id][i]&&dp[id][v[j]])
                {
                    if(i-v[j]>0)
                        dp[ids][i-v[j]]++;
                    if(i+v[j]<50005)
                        dp[ids][i+v[j]]++;
                }
            }
            for(int k=0;k<=((m+1)*m)/2*((n+1)*n)/2;k++)
                {
                    dp[ids][k]+=dp[id][k];
                    dp[id][k]=0;
                }
            swap(ids,id);
        }
    printf("%d",dp[id][x]);


    return 0;
}