codeforce 문제 888E 시간초과가 됩니다( meet in the middle 알고리즘)

모든 합의 경우의수는 2^35이지만 나누어서 대략 2^19, 2^19인데요. (배열크기도 2^20개 두개)

 그러나 정답을 찾기위해 중첩 for문을 돌릴 때 시간초과가 걸립니다. (맨마지막부분)

생각을 곰곰히 해보았는데, 어쨌든 중첩 for문도 모든 경우의수를 하니까 애초에 2^19 * 2^19크기에서 시간초과가 납니다만, 제가 그것을 모면하기 위해 같은 수는 뛰어넘어가라고 명령을 내렸습니다. // while(j<idx2-1 && arr2[j]==arr2[j+1]) j++;

그전에보시면 모든 경우의수의 합을 모듈러 연산했기 떄문에, 같은것이 반드시 존재할 수도 있고 아닐 수도있습니다.

modular가 굉장히 작으면 같은 크기의 합도 많이 생기겠지요 (패스할 수가 많음)

그러나 문제는 모듈러가 굉장히 클때, 특히 10억일 때 경우의수는 실제로 10억만큼 존재할 수 있고

또 10억만큼 존재할 수 있었습니다. 실제로 예로 m이 10억값이 들어올 때 시간초과가 납니다. ㅠ.ㅠ.ㅠ.ㅠ

맨 아래의 처리(정답을 구하는 처리)를 어떻게 해야할지 모르겠습니다.

이제까지 풀었던 BOJ의 meet in the middle(????) 수들의합2, 부분합, 소수의 연속합, 부분집합의 합2, 합이 0인 네정수 등등은 특정 수가 되는 것을 찾는거여서 왠지 익숙했거든요... 그런데 모듈러 연산을 했을 때 최대의 값을 찾는것은 어떻게 해야할 지 모르겠습니다..

사실 그것을 구하기위해 완전탐색을 (for 문두개)로 돌렸거든요...

코드는 아래와 같습니다.

#include <stdio.h>
#include <stdlib.h>
int a[35], n, m, arr1[1<<20], arr2[1<<20];
int idx1, idx2;
int mycmp(const void* a, const void* b) { return *(int *)a - *(int *)b;}
void dfs(int i, int sum, int type){
  if (type && i==n) {arr2[idx2++] = sum; return;}
  else if (!type && i==n/2) {arr1[idx1++]= sum; return ; }

  dfs(i+1, (sum+a[i])%m , type);
  dfs(i+1, sum, type);
}
int main(){
  scanf("%d %d", &n, &m);
  for (int i=0; i<n; i++){
    scanf("%d", &a[i]);
    a[i]%=m;
  }
  qsort (a, n, sizeof(int), mycmp);

  dfs(0, 0, 0);
  dfs(n/2, 0, 1);
  arr1[idx1++]=0;
  arr2[idx2++]=0;

  for (int i=0; i<idx1; i++) arr1[i]%=m;
  for (int i=0; i<idx2; i++) arr2[i]%=m;

  qsort(arr1, idx1, sizeof(int), mycmp);
  qsort(arr2, idx2, sizeof(int), mycmp);

  int ans=0;
  for (int i=0; i<idx1; i++){
    for (int j=0; j<idx2; j++){
      int tmp= (arr1[i]+arr2[j])%m;
      if (tmp > ans) ans=tmp;
      while(j<idx2-1 && arr2[j]==arr2[j+1]) j++;
    }
    while( i<idx1-1 && arr1[i]==arr1[i+1]) i++;
  }

  printf("%d\n", ans);
}