提出 #73219476

---

ソースコード 拡げる

#include <bits/stdc++.h>
using ll = long long int;
using namespace std;
ll read()
{
    ll k = 0,f = 1;
    char c = getchar();
    while(c < '0' || c > '9')
    {
        if(c == '-')f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')k = k * 10 + c - '0',c = getchar();
    return k * f; // 别忘记标记的负数要乘进去
}
// 调用时用 n=in();
void print(ll x)
{
    if(x < 0)putchar('-'),x = -x;
    if(x < 10)putchar(x + '0');
    else print(x / 10),putchar(x % 10 + '0');
}
// 直接调用 out(n) 就行了
void solve(){
   int n = read(), m = read();
   vector<ll>w(n);//每个包裹的重量
   vector<ll>c(m);//每辆卡车的限重
   for(int i = 0; i < n; i++)w[i] = read();
   for(int j = 0; j < m; j++)c[j] = read();
   vector<ll>W(1 << n);//每种组合的总重量
   for(int i = 0; i < (1 << n); i++){
    for(int j = 0; j < n; j++){
        if((i >> j) & 1){
            W[i] += w[j];
        }
    }
   }
   int dp[1 << 16][16];
   for(int i = 0; i < (1 << 16); i++){
    for(int j = 0; j < 16; j++){
        dp[i][j] = -1;
    }
   }
   auto dfs = [&](auto&& self, int status, int pos) -> int{
    if(status == 0)return 1;
    if(pos >= m)return 0;
    if(dp[status][pos] != -1)return dp[status][pos];
    if(self(self, status, pos + 1)){
        return dp[status][pos] = 1;
    }
    for(int sub = status; sub ; sub = (sub - 1) & status){
        if(W[sub] <= c[pos]){
            if(self(self, status ^ sub, pos + 1)){
                return dp[status][pos] = 1;
            }
        }
    }
    return dp[status][pos] = 0;
   };
   if(dfs(dfs, (1 << n) - 1, 0)){
    cout << "Yes";
   }
   else{
    cout << "No";
   }
}
signed main(){
    int T = 1;
    while(T--){
        solve();
    }
    return 0;
}

提出情報

ジャッジ結果