01

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 40, M = 300000;
 5 int n, mod, a[N], ans;
 6 int p1[M], p2[M], idx1, idx2;
 7 
 8 void dfs1(int p, int sum)
 9 {
10     if (p == n / 2 + 1)
11     {
12         p1[++ idx1] = sum;
13         return;
14     }
15     dfs1(p+1, sum), dfs1(p+1, (a[p] + sum) % mod);
16 }
17 
18 void dfs2(int p, unsigned int sum)
19 {
20     if (p == n + 1)
21     {
22         p2[++ idx2] = sum;
23         return;
24     }
25     dfs2(p+1, sum), dfs2(p+1, (a[p] + sum) % mod);
26 }
27 
28 int main()
29 {
30     scanf("%d %d", &n, &mod);
31     for (int i=1; i<=n; i++)
32         scanf("%d", &a[i]);
33         
34     if (n == 1)
35     {
36         printf("%d\n", a[1] % mod);
37         return 0;
38     }    
39         
40     dfs1(1, 0), dfs2(n/2+1, 0);
41     
42     sort(p1+1, p1+idx1+1);
43     sort(p2+1, p2+idx2+1);
44     
45     int l = idx1;
46     for (int r=1; r<=idx2; r++)
47     {
48         while (l != 1 && p1[l] + p2[r] >= mod) -- l;
49         ans = max(ans, p1[l] + p2[r]);
50     }
51     ans = max(ans, p1[idx1] + p2[idx2] - mod);
52     
53     printf("%d\n", ans);
54     return 0;
55 }