[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);
}