Submission #901278

#	Time	Username	Problem	Language	Result	Execution time	Memory
901278		StefanL2005	Bank (IZhO14_bank)	C++14	100 / 100	115 ms	12132 KiB

bank

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

int bin_read(int k, vector<int> &v, int l)
{
    if (k == 0)
       return 0;
    if ((k & 1) == 1)
        return v[l] + bin_read((k >> 1), v, l + 1);
    return bin_read((k >> 1), v, l + 1);
}

int in_range(pair<int,int> range, vector<int> &v)
{
    if (range.first == 0)
        return v[range.second];
    return v[range.second] - v[range.first - 1];
}
bool Check(pair<int,int> range, int K, vector<vector<int>> &VarSum, vector<int> &Verif, vector<int> &PrePop, vector<int> &Money)
{
    if (range.first == range.second)
        return true;

    int m = (range.first + range.second) / 2;
    pair<int,int> left = make_pair(range.first, m);
    pair<int,int> right = make_pair(m + 1, range.second);
    int l = in_range(left, PrePop);
    int r = in_range(right, PrePop);

    for (int i = 0; i < VarSum[l].size(); i++)
    {
        int a = VarSum[l][i];
        int b = K - a;

        if ((a | K) != K)
            continue;
        if (bin_read(b, Money, 0) != r)
            continue;
        if (Verif[a] == -1)
            Verif[a] = Check(left, a, VarSum, Verif, PrePop, Money);
        if (Verif[b] == -1)
            Verif[b] = Check(right, b, VarSum, Verif, PrePop, Money);

        if (Verif[b] + Verif[a] == 2)
            return true;
    }
    return false;
}
int main()
{
    int n, m, s = 0; cin>> n >> m;
    vector<int> People(n), Money(m);

    for (int i = 0; i < n; i++)
        cin>> People[i];
    for (int i = 0; i < m; i++)
    {
        cin>> Money[i];
        s+= Money[i];
    }

    lm = (1 << m);
    pair<int,int> start = make_pair(0, n - 1);
    vector<int> PrePop(n);
    vector<int> Verif(lm, -1);
    //-1 undeclared, 0 false, 1 true;
    vector<vector<int>> VarSum(s + 1);

    PrePop[0] = People[0];
    for (int i = 1; i < n; i++)
        PrePop[i] = PrePop[i - 1] + People[i];
    for (int i = 0; i < lm; i++)
        VarSum[bin_read(i, Money, 0)].push_back(i);

    bool ok = false;

    if (PrePop[n - 1] <= s)
        for (int i = 0; i < VarSum[PrePop[n - 1]].size(); i++)
        {
            int node = VarSum[PrePop[n - 1]][i];

            if (Check(start, node, VarSum, Verif, PrePop, Money) == true)
            {
                ok = true;
                break;
            }
        }

    if (!ok)
        cout<< "NO";
    else
        cout<< "YES";
    return 0;
}

Compilation message (stderr)

bank.cpp: In function 'bool Check(std::pair<int, int>, int, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
bank.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < VarSum[l].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
bank.cpp: In function 'int main()':
bank.cpp:81:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int i = 0; i < VarSum[PrePop[n - 1]].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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