Submission #882125

#	Time	Username	Problem	Language	Result	Execution time	Memory
882125		StefanL2005	Bank (IZhO14_bank)	C++14	0 / 100	116 ms	262144 KiB

bank

#include <bits/stdc++.h>
using namespace std;
ifstream in("bank.in");
ofstream out("bank.out");

struct keyData{
    int key, sum; 
};

int readBin(int k, vector<int> &Money)
{
    int pos = 0, sum = 0;

    while (k != 0)
    {
        if ( (k & 1) == 1)
            sum+= Money[pos];
        pos++;
        k = (k >> 1);
    }

    return sum;
}

bool rule(keyData A, keyData B)
{
    if (A.sum == B.sum)
        return A.key < B.key;
    return A.sum < B.sum;
}

bool FindAnswer(int L, int n, int K, vector<keyData> &Pos, vector<int> &Start)
{
    if (L == n)
        return true;
    
    int i = Start[L];

    while (i < Pos.size() && Pos[i].sum == Pos[Start[L]].sum)
    {
        if ( (K & Pos[i].key) == 0)
            if(FindAnswer(L + 1, n, K + Pos[i].key, Pos, Start))
                return true;    
        i++;
    }

    return false;
}

int main()
{
    int n, m; in>> n >> m;
    vector<int> People(n), Money(m);
    
    int var = (1 << m);
    vector<keyData> Pos(var);

    for (int i = 0; i < n; i++)
        in>> People[i];
    for (int i = 0; i < m; i++)
        in>> Money[i];

    for (int i = 0; i < var; i++)
    {
        Pos[i].key = i;
        Pos[i].sum = readBin(i, Money);
    }

    sort(Pos.begin(), Pos.end(), rule);

    vector<int> start(n);
    for (int i = 0; i < n; i++)
    {
        keyData A; A.key = 0; A.sum = People[i];
        start[i] = lower_bound(Pos.begin(), Pos.end(), A, rule) - Pos.begin();
    
        if (Pos[start[i]].sum != People[i])
        {
            out<< "NO";
            return 0;
        }
    }
    
    if (FindAnswer(0, n, 0, Pos, start))
        out<< "YES";
    else
        out<< "NO";

    return 0;
}

Compilation message (stderr)

bank.cpp: In function 'bool FindAnswer(int, int, int, std::vector<keyData>&, std::vector<int>&)':
bank.cpp:39:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<keyData>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     while (i < Pos.size() && Pos[i].sum == Pos[Start[L]].sum)
      |            ~~^~~~~~~~~~~~

• Subtask 1: 0 / 19
• Subtask 2: 0 / 25
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29