Submission #1176700

#TimeUsernameProblemLanguageResultExecution timeMemory
1176700giabao249Bank (IZhO14_bank)C++20
100 / 100
352 ms23936 KiB
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define int long long
#define FOR(i , a , b) for(int i = a ; i < b ; i++)
#define REP(i , a , b) for(int i = a ; i <= b ; i++)
#define FORD(i , a , b) for(int i = a ; i >= b ; i--)
#define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define el '\n'
#define all(x) x.begin(), x.end()
#define bit(x) (1 << (x))
#define log(...) logger(#__VA_ARGS__, __VA_ARGS__)
const int inf = 1e18;
const int base = 311;
const int mod = 1e9 + 7;
template <typename... Args> void logger(string vars, Args&&... values);
template<class T> bool ckmin(T& a, const T& b)
{
    return b < a ? a = b, 1 : 0;
}
template<class T> bool ckmax(T& a, const T& b)
{
    return a < b ? a = b, 1 : 0;
}
//Think
const int N = 21;
string name = "Task";
bool f[N][bit(N)];
int sum[bit(N)] ;
int n, m;
int cost[N], staff[N];
vector<pii> le, ri;
int half = m / 2;
vector<vector<int>> valid;
void prepare()
{
    valid.resize(n);
    FOR(mask, 0,  bit(half)) {
        int s = 0;
        FOR(i, 0, half) {
            if(mask & bit(i))
                s += cost[i];
        }
        le.push_back({s, mask});
    }
    FOR(mask, 0,  bit(m - half)) {
        int s = 0;
        FOR(i, 0, m - half) {
            if(mask & bit(i))
                s += cost[i + half];
        }
        ri.push_back({s, mask});
    }
    FOR(i, 0, n) {
        for(auto l : le) {
            for(auto r : ri) {
//                    log(l.first, r.first);
                if(l.first + r.first == staff[i]) {
                    int full = l.second | (r.second << half);
                    valid[i].push_back(full);
//                    log(i, full);
                }
            }
        }
    }
}
void GOTO_OLP2025()
{
    cin >> n >> m;
    FOR(i, 0, n) cin >> staff[i];
    FOR(i, 0, m) cin >> cost[i];
    prepare();
    f[0][0] = 1;
    FOR(mask, 0, bit(m)) {
        FOR(i, 0, n) {
            if(!f[i][mask]) continue;
            for(auto x : valid[i]) {
                if(!(x & mask)) {
                    f[i + 1][x | mask] = 1;
                }
            }

        }
    }
    FOR(mask , 0 , bit(m)){
        if(f[n][mask]){
            cout << "YES" << el;
            return;
        }
    }
    cout << "NO" << el;
}

void file(string s)
{
    string in = s + ".in";
    string out = s + ".out";
    if(fopen(in.c_str(), "r")) {
        freopen(in.c_str(), "r", stdin);
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    file(name);
    //int t ; cin >> t;
    //while(t--)
    GOTO_OLP2025();
    return 0;
}
template <typename... Args>
void logger(string vars, Args&&... values)
{
    cerr << "[";
    stringstream ss(vars);
    string var;
    vector<string> varNames;
    while (getline(ss, var, ',')) {
        while (!var.empty() && var.front() == ' ') var.erase(0, 1);
        varNames.push_back(var);
    }
    string delim = "";
    size_t i = 0;
    ((cerr << delim << varNames[i++] << " = " << values, delim = ", "), ...);
    cerr << "]\n";
}

Compilation message (stderr)

bank.cpp: In function 'void file(std::string)':
bank.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen(in.c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...