Submission #901255

#TimeUsernameProblemLanguageResultExecution timeMemory
901255StefanL2005Bank (IZhO14_bank)C++14
0 / 100
1 ms604 KiB
#include <bits/stdc++.h>
using namespace std;
ifstream in("bank.in");
ofstream out("bank.out");
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 (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; in>> n >> m;
    vector<int> People(n), Money(m);

    for (int i = 0; i < n; i++)
        in>> People[i];
    for (int i = 0; i < m; i++)
    {
        in>> 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;
    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) == 1)
        {
            ok = true;
            break;
        }
    }

    if (!ok)
        out<< "NO";
    else
        out<< "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:31:9: warning: unused variable 'r' [-Wunused-variable]
   31 |     int r = in_range(right, PrePop);
      |         ^
bank.cpp: In function 'int main()':
bank.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i = 0; i < VarSum[PrePop[n - 1]].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...