Cod sursa(job #2591895)

Utilizator isa_tudor_andreiAndrei Tudor isa_tudor_andrei Data 31 martie 2020 17:17:16
Problema Diamant Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 20;
const int NORM = NMAX * NMAX * (NMAX + 1) * (NMAX + 1) / 4;
const int MOD = 1e5;
int dp[NMAX * NMAX + 5][NORM * 2 + 5];

int main() {
    int n, m, x;
    fin>>n>>m>>x;
    dp[1][-1 + NORM] = dp[1][NORM] = dp[1][1 + NORM] = 1;
    for( int i = 1; i <= n; i ++ ) {
      for( int j = 1 + (i == 1); j <= m; j ++ ) {
        int poz = (i - 1) * m + j;
        for( int k = -1; k <= 1; k ++ ) {
          int newcost = k * (i * j);
          for( int cost = 0; cost <= 2 * NORM; cost ++ ) {
            if( cost - newcost >= 0 && cost - newcost <= 2 * NORM )
              dp[poz][cost] = (dp[poz - 1][cost] + dp[poz - 1][cost - newcost]) % MOD;
          }
        }
      }
    }
    fout<<dp[n * m][x + NORM];
    return 0;
}