Cod sursa(job #3228913)

Utilizator BreabanDanielBreaban Daniel-Vasile BreabanDaniel Data 11 mai 2024 23:28:19
Problema Diamant Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <iostream>
#include <vector>
#define NMAX 100000
#define MOD 10000
using namespace std;
ifstream fin("diamant.in");
ofstream fout("diamant.out");
int dp[NMAX*2+9];
int dp1[NMAX*2+9];
int n,m,k,sum;
int main()
{
    fin>>n>>m>>k;
    dp[NMAX]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            sum+=i*j;

    if(k>0)
    {
        if(k>sum)
        {
            fout<<0;
            return 0;
        }
    }
    else
    {
        if(sum<-1*k)
        {
            fout<<0;
            return 0;
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int aux=i*j,a=0,b=0;
            for(int g=NMAX*2;g>=aux;g--)
            {
                dp1[g]+=dp[g-aux];
                dp1[g]+=dp[g+aux];
            }
            for(int g=NMAX*2;g>=aux;g--)
            {
                dp[g]=dp1[g];
            }
        }

    fout<<dp[NMAX+k];
    return 0;
}