Cod sursa(job #48828)

Utilizator GabiAlb Gabriel Gabi Data 5 aprilie 2007 08:54:38
Problema Diamant Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
using namespace std;

int g[100], c[100];
int n, m, x;
int cmax[100], v[100][100];

int main()
{
    ifstream fin("diamant.in");
    ofstream fout("diamant.out");
    
    fin >> n >> m >> x;
    
    int t = 0;
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        g[++t] = i * j;
        
    for (int i = 1; i <= n*m; i++)
        c[i] = 0;
        
    int s, k, i;
    
    for (s = 1; s <= x; s++) cmax[s] = -1;
    for (s = 1; s <= x; s++)
        for (i = 1; i <= n*m; i++)
            if (g[i] <= s && cmax[s-g[i]] != -1 && !v[s-g[i]][i])
                if (cmax[s] < c[i] + cmax[s-g[i]])
                {
                    cmax[s] = c[i] + cmax[s-g[i]];
                    for (k = 1; k <= n*m; k++)
                        v[s][k] = v[s-g[i]][k];
                    v[s][i] = 1;
                }
                
    int cnt = 0;
    for (int i = 1; i <= n*m; i++)
        if (v[x][i]) cnt++;

    fout << cnt << "\n";
    fout.close();
    fin.close();
    return 0;
}