Submission #13049396

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define mp make_pair
#define deb(x) cout<< #x << " " << x << "\n";
#define INF 9223372036854775807
const ll mod=1e9+7;


int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll n,m,x;
    cin>>n>>m>>x;
    vector<ll> c(n);
    vector<vector<ll>> a(n,vector<ll>(m));
    for(ll i=0;i<n;i++){
        cin>>c[i];
        for(ll j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    ll ans=INF;
    for(ll i=0;i<1<<n;i++){
        vector<ll> b(m);
        ll sum=0;
        for(ll j=0;j<n;j++){
            if(1<<j&i){
                sum+=c[j];
                for(ll k=0;k<m;k++)
                    b[k]+=a[j][k];
            }
        }
        ll f=1;
        for(ll j=0;j<m;j++){
            if(b[j]<x){
                f=0;
                break;
            }
        }
        if(!f) continue;
        ans=min(ans,sum);
    }
    if(ans==INF)
        cout<<-1;
    else
        cout<<ans;


    return 0;
}

Submission Info

Judge Result