Cod sursa(job #2880552)

Utilizator PalffyLehelPalffy Lehel PalffyLehel Data 29 martie 2022 21:06:29
Problema Diamant Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <iostream>
#include <fstream>
#include <list>

using namespace std;

int main()
{
    ifstream f("diamant.in");
    ofstream g("diamant.out");
    int n, m, x;
    f >> n >> m >> x;

    int maxHossz = 44100;
    int terkep[2 * maxHossz + 1];
    fill_n(terkep, 2 * maxHossz + 1, 0);

    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 = max(it->second, it->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 = max(it->second, it->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;
}