[Codeforces] E. Maximum Subsequence

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. Maximum Subsequence
Source            : Codeforces
Category          : Meet In The Middle
Algorithm         : Coin Change
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll            long long
#define vll           vector <ll>
 
vll firstHalf, secondHalf;
int n;
ll arr[40], m;
ll arr1[20], arr2[20];
 
inline void subset(vll &vec, ll arr[], int pos, int len, ll sum)
{
       if (pos > len)
       {
              vec.emplace_back(sum);
              return;
       }
       subset(vec, arr, pos+1, len, sum);
       subset(vec, arr, pos+1, len, (sum + arr[pos]) % m);
}
 
inline void makeUnique(vector <ll> &vec)
{
       sort(vec.begin(), vec.end());
       vec.erase(unique(vec.begin(), vec.end()), vec.end());
}
 
int main()
{
       //freopen("in.txt", "r", stdin);
 
       scanf("%d %lld", &n, &m);
       for (int i = 1; i <= n; i++) scanf("%lld", arr+i);
       for (int i = 1; i <= n/2; i++) arr1[i] = arr[i];
       for (int i = n/2+1, j = 1; i <= n; i++, j++) arr2[j] = arr[i];
 
       subset(firstHalf, arr1, 1, n/2, 0);
       subset(secondHalf, arr2, 1, n - n/2, 0);
 
       makeUnique(firstHalf);
       makeUnique(secondHalf);
 
       ll maxi = -1e18;
       for (ll f : firstHalf)
       {
              ll ff = m - f;
              auto s = lower_bound(secondHalf.begin(), secondHalf.end(), ff);
              if (s == secondHalf.end() || *s >= ff) s--;
              ll val = (f + *s) % m;
              if (maxi < val) maxi = val;
       }
       printf("%lld", maxi);
}
 

[toph.co] The Perfect Collection

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : The Perfect Collection
Source            : toph.co
Category          : Dynamic Programing
Algorithm         : Coin Change
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
int dp[100+5][100+5][2050];
bool memoize[100+5][100+5][2050];
 
int n, q, k, arr[100+5];
 
inline int minimumXor(int pos, int take, int xorVal)
{
	if (take == 0) return xorVal;
	if (pos > n or take < 0) return INT_MAX;
	int &ret = dp[pos][take][xorVal];
	bool &mem = memoize[pos][take][xorVal];
	if (mem) return ret;
	mem = 1;
	int choice1, choice2;
	choice1 = minimumXor(pos+1, take - 1, xorVal xor arr[pos]);
	choice2 = minimumXor(pos+1, take, xorVal);
	return ret = min(choice1, choice2);
}
 
int main()
{
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> arr[i];
	while (q--)
	{
		cin >> k;
		cout << minimumXor(1, k, 0) << endl;
	}
}