Cod sursa(job #3183292)

Utilizator KarinaDKarina Dumitrescu KarinaD Data 11 decembrie 2023 14:05:45
Problema Diamant Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 2e5;
int dp[N];

int main () {
    
    int n, m, x;
    long long sum = 0;
    
    fin >> n >> m >> x;
    
    if ( x < 0 )
        x = -x;
    
    for ( int i = 1; i <= n; i++ )
        for ( int j = 1; j <= m; j++ )
            sum = sum + i * j;
    
    if ( x > sum )
        fout << "0";
    else if ( x == sum )
        fout << "1";
    
    else {
        
        dp[0] = 1;
        
        for ( int i = 1; i <= n; i++ )
            for ( int j = 1; j <= m; j++ )
                for ( long long s = sum - x; s >= i * j; s-- ) {
                    dp[s] = dp[s] + dp[s - i * j];
                    if ( s >= 2 * i * j )
                        dp[s] = dp[s] + dp[s - 2 * i * j];
                }
        
        fout << dp[sum - x];
    }
    
    return 0;
}