CSES - Aalto Competitive Programming 2024 - wk12 Homework - Results
Submission details
Task:Missing Coin Sum
Sender:Nallue
Submission time:2024-11-23 16:06:54 +0200
Language:C++ (C++11)
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:28:39: error: use of deleted function 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = std::pair<int, int>; _Tp = bool; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, bool> >]'
   28 |     unordered_map<pair<int,int>,bool> m;
      |                                       ^
In file included from /usr/include/c++/11/unordered_map:47,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:117,
                 from input/code.cpp:1:
/usr/include/c++/11/bits/unordered_map.h:141:7: note: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = std::pair<int, int>; _Tp = bool; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, bool> >]' is implicitly deleted because...

Code

#include <bits/stdc++.h>

using namespace std;

bool subsetExists(const vector<int>& vec, int final, int sum, map<pair<int,int>,bool>& m){
    if(sum == 0) return true;
    if(sum < 0) return false;
    if(final == 0) return false;

    auto f = m.find(make_pair(final-1,sum));
    bool first = (f != m.end() and f->second);

    auto s = m.find(make_pair(final-1,sum-vec[final-1]));
    bool second = (s != m.end() and s->second);

    bool temp =  first or second or subsetExists(vec, final-1, sum, m) or subsetExists(vec, final-1, sum-vec[final-1], m);
    m[make_pair(final,sum)] = temp;
    return temp;
}


int main(){
    int n;
    cin >> n;
    vector<int> vec(n);
    for(int i=0;i<n; i++) cin >> vec[i];

    unordered_map<pair<int,int>,bool> m;

    int idx=0;
    while(subsetExists(vec, n, idx, m)) idx += 1;

    cout<< idx << endl;


}