Submission #1324455

#TimeUsernameProblemLanguageResultExecution timeMemory
1324455SSKMFBank (IZhO14_bank)C++20
19 / 100
53 ms16836 KiB
#include <bits/stdc++.h>
using namespace std;

int dorit[20] , termen[20] , suma[1 << 20] , modalitati_2[1 << 20];
long long modalitati_1[1 << 20];

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int cantitate[2];
    cin >> cantitate[0] >> cantitate[1];

    for (int indice = 0 ; indice < cantitate[0] ; indice++)
        { cin >> dorit[indice]; }
    for (int indice = 0 ; indice < cantitate[1] ; indice++)
        { cin >> termen[indice]; }

    for (int masca = 1 , exponent = 0 ; masca < (1 << cantitate[1]) ; masca++)
    {
        if (masca & (1 << (exponent + 1)))
            { exponent += 1; }

        suma[masca] = suma[masca ^ (1 << exponent)] + termen[exponent];
    }

    modalitati_1[0] = 1;
    for (int indice = 0 ; indice < cantitate[0] ; indice++)
    {
        for (int masca = 0 ; masca < (1 << cantitate[1]) ; masca++) {
            if (suma[masca] == dorit[indice])
                { modalitati_2[masca] = 1; }
            else
                { modalitati_2[masca] = 0; }
        }

        for (int putere = 1 ; putere < (1 << cantitate[1]) ; putere <<= 1) {
            for (int masca = 0 ; masca < (1 << cantitate[1]) ; masca++) {
                if (masca & putere)
                { 
                    modalitati_1[masca] += modalitati_1[masca ^ putere];
                    modalitati_2[masca] += modalitati_2[masca ^ putere];    
                }
            }
        }

        for (int masca = 0 ; masca < (1 << cantitate[1]) ; masca++)
            { modalitati_1[masca] *= modalitati_2[masca]; }
            
        for (int putere = 1 ; putere < (1 << cantitate[1]) ; putere <<= 1) {
            for (int masca = 0 ; masca < (1 << cantitate[1]) ; masca++) {
                if (masca & putere)
                    { modalitati_1[masca] -= modalitati_1[masca ^ putere]; }
            }
        }

        bool gasit = false;
        for (int masca = 0 ; masca < (1 << cantitate[1]) ; masca++) {
            if (suma[masca] == dorit[indice] && modalitati_1[masca])
                { modalitati_1[masca] = 1; gasit = true; }
            else
                { modalitati_1[masca] = 0; }
        }

        if (!gasit)
            { cout << "NO"; return 0; }
    }

    cout << "YES";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...