Cod sursa(job #1900437)

Utilizator trutruvasilicaHuhurez Marius trutruvasilica Data 3 martie 2017 13:05:56
Problema Diamant Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("diamant.in");
ofstream fout("diamant.out");
int pls[2][44105],mns[2][44105],cost[1001];
int main()
{
    int n,m,x,i,j;
    fin>>n>>m>>x;
    int rez=0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            rez+=i*j;
            cost[(i-1)*n+j]=i*j;
            pls[0][i*j]=1;
            mns[0][i*j]=1;
        }
    }
    pls[0][0]=mns[0][0]=1;
    int tot=n*m;
    int ct,ant;
    for(i=2;i<=tot;i++)
    {
        ct=(i+1)&1;
        ant=i&1;
        for(j=1;j<=rez;j++)
        {
            pls[ct][j]+=pls[ant][j];
            if(j>=cost[i]) pls[ct][j]+=pls[ant][j-cost[i]];
            else pls[ct][j]+=mns[ant][cost[i]-j];
            mns[ct][j]+=mns[ant][j];
            if(j>=cost[i]) mns[ct][j]+=mns[ant][j-cost[i]];
            else mns[ct][j]+=pls[ant][cost[i]-j];
        }
    }
    if(x>0 && x>rez) fout<<"0";
    else if(x<0 && -x >rez) fout<<"0";
    else
    {
        if(x>0) fout<<pls[ct][x];
        else fout<<mns[ct][-x];
    }
}