Skip to content

Instantly share code, notes, and snippets.

@medhruv7
Created May 21, 2020 22:34
Show Gist options
  • Save medhruv7/5e7525dbc6289b261d6e6ff6060967c3 to your computer and use it in GitHub Desktop.
Save medhruv7/5e7525dbc6289b261d6e6ff6060967c3 to your computer and use it in GitHub Desktop.
//dhruv
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ffor(i,n) for(int i = 0;i < (n); ++i)
#define fro(i,j,n) for(int i = (j);i < (n); ++i)
#define all(v) v.begin(),v.end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define ff first
#define ss second
const int mod = 1e9 + 7;
template<typename T>
T binpow(T a,T b,T mod){
T res = 1;
while(b){
if(b&1){
res = (res*a)%mod;
}
b /= 2;
(a *= a) %= mod;
}
return res;
}
template<typename T>
T binpow(T a,T b){
T res = 1;
while(b){
if(b&1){
res = (res*a);
}
b /= 2;
a *= a;
}
return res;
}
template<typename T>
T add(T a,T b){
return (a + b)%mod;
}
template<typename T>
T sub(T a,T b){
return add(a,mod - b);
}
template<typename T>
T mul(T a,T b){
return (a*b)%mod;
}
int make_int(string s){
int x = 0;
reverse(s.begin(),s.end());
string tmp = s;
for(int i = 0;i < s.length(); ++i){
x *= 10;
x += (int)(tmp.back() - '0');
tmp.pop_back();
}
return x;
}
string make_string(int s){
string x;
while(s){
x.push_back(char(s%10 + '0'));
s /= 10;
}
reverse(x.begin(),x.end());
return x;
}
const int inf = 1e18 + 5;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,x;
cin >> n >> x;
int a[n];
ffor(i,n) cin >> a[i];
pair<int,int> dp[1<<n];
dp[0] = {1,0};
for(int i = 1;i < (1<<n); ++i){
dp[i] = {n + 1,0};
for(int j = 0;j < n; ++j){
if((1<<j)&i){
int rides = 0;
int space = 0;
// remove this element and put it in the existing subset (i^(1<<j)) at last
auto option = dp[(1<<j)^i];
if(option.ss + a[j] <= x){
option.ss += a[j];
}else{
option.ff++;
option.ss = a[j];
}
dp[i] = min(dp[i],option);
}
}
}
cout << dp[(1<<n) - 1].ff;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment