Cod sursa(job #2458829)

Utilizator Senth30Denis-Florin Cringanu Senth30 Data 21 septembrie 2019 16:32:51
Problema Diamant Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <bits/stdc++.h>
#define MAX 131072

using namespace std;
const int NMAX = 45000;

FILE *IN, *OUT;

int N, M, X, nrMax;
int dp[2][NMAX];

int pos, sign, out;
char f[MAX], Out[MAX], str[10];

inline void Write_Ch(char ch){
    Out[out++] = ch;
    if(out == MAX)
        fwrite(Out, MAX, 1, OUT), out = 0;
}

inline void Write_Int(int nr){
    int x = 0;
    if(nr < 0) Write_Ch('-'), nr = -nr;
    do{
        str[x++] = nr % 10 + '0';
        nr /= 10;
    } while(nr);
    while(x > 0)
        Write_Ch(str[--x]);
}

inline void Read(int &nr){
    sign = 0;
    nr = 0;
    while(f[pos] < '0' || f[pos] > '9'){
        if(f[pos] == '-') sign = 1;
        pos++;
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    while(f[pos] >= '0' && f[pos] <= '9'){
        nr = 10 * nr + f[pos++] - '0';
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    if(sign) nr =- nr;
}

int main(){

    IN = fopen("diamant.in", "r");
    OUT = fopen("diamant.out", "w");

    Read(N); Read(M); Read(X);
    if(X < 0) X *= -1;
    if(X > 44100){
        Write_Int(0);
        if(out > 0) fwrite(Out, 1, out, OUT);
        return 0;
    }

    nrMax = 1;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            int cnt = i * j;
            int pMax = nrMax;
            for(int k = 1; k <= nrMax; k++){
                if(cnt >= k){
                    dp[1][cnt - k] += dp[0][k];
                    dp[1][cnt + k] += dp[0][k];
                } else {
                    dp[1][k - cnt] += dp[0][k];
                    dp[1][k + cnt] += dp[0][k];
                }
                if(cnt + k > pMax) pMax = cnt + k;
            }
            dp[1][cnt] = 1;
            nrMax = pMax;
            for(int k = 1; k <= nrMax; k++){
                dp[0][k] += dp[1][k];
                dp[1][k] = 0;
            }
        }
    }
    Write_Int(dp[0][X]);

    if(out > 0) fwrite(Out, 1, out, OUT);

    return 0;
}