Cod sursa(job #2881093)

Utilizator PalffyLehelPalffy Lehel PalffyLehel Data 30 martie 2022 11:38:55
Problema Diamant Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.39 kb
#include <iostream>
#include <fstream>
#include <list>
#include <cmath>

using namespace std;

int main()
{
    ifstream f("diamant.in");
    ofstream g("diamant.out");

    int n, m, x;
    f >> n >> m >> x;

    int nagyszam = n * (n + 1) / 2 *
                   m * (m + 1) / 2;
    int nagytomb[2 * nagyszam + 1];
    fill_n(nagytomb, 2 * nagyszam + 1, 0);
    nagytomb[0] = 1;

    int nagytombMentes[2 * nagyszam + 1];
    fill_n(nagytombMentes, 2 * nagyszam + 1, 0);

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            copy(nagytomb, nagytomb + nagyszam, nagytombMentes);

            for (int k = nagyszam; k >= 0; k--)
            {
                nagytomb[k] = nagytombMentes[(int)abs(k - i * j)] + nagytombMentes[k] + nagytombMentes[k + i * j];
            }

//            for (int i = 0; i <= nagyszam; i++)
//            {
//                cout << nagytomb[i] << " ";
//            }
//            cout << endl;
        }
    }

    g << nagytomb[(int)abs(x)];
//    cout << "|" << nagytomb[(int)abs(x)] << "|" << endl;

   /* list<pair<pair<int, int>, int> > elofordulasok;
    list<pair<pair<int, int>, int> > :: iterator it;
    list<pair<pair<int, int>, int> > :: iterator it2;

    list<pair<pair<int, int>, int> > frontFiller;
    list<pair<pair<int, int>, int> > backFiller;

    elofordulasok.push_back(make_pair(make_pair(0, 1), 0));

    int elem, plusz, minusz;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            elem = i * j;

            for (it = elofordulasok.begin(); it != elofordulasok.end(); it++)
            {
                minusz = it->first.first - elem;
                plusz = it->first.first + elem;

                if (minusz < elofordulasok.front().first.first)
                {
                    frontFiller.push_back(make_pair(make_pair(minusz, it->first.second), 0));
                }
                else
                {
                    it2 = it;
                    advance(it2, elem * -1);
                    it2->second = 1 + it->first.second - it2->first.second;
                }

                if (plusz > elofordulasok.back().first.first)
                {
                    backFiller.push_back(make_pair(make_pair(plusz, it->first.second), 0));
                }
                else
                {
                    it2 = it;
                    advance(it2, elem);
                    it2->second = 1 + it->first.second - it2->first.second;
                }
            }


            frontFiller.insert(frontFiller.end(), elofordulasok.begin(), elofordulasok.end());
            elofordulasok.clear();
            elofordulasok.insert(elofordulasok.begin(), frontFiller.begin(), frontFiller.end());
            elofordulasok.insert(elofordulasok.end(), backFiller.begin(), backFiller.end());

            frontFiller.clear();
            backFiller.clear();

            for (it = elofordulasok.begin(); it != elofordulasok.end(); it++)
            {
                it->first.second += it->second;
                it->second = 0;
            }
        }
    }

    for (it = elofordulasok.begin(); it != elofordulasok.end(); it++)
    {
        if (it->first.first == x)
        {
            g << it->first.second;
            break;
        }
    }*/

    return 0;
}