Spoj - 배열의 최대 부분 집합

Question

이 spoj 문제를 해결하고있었습니다. http://www.spoj.com/problems/MAXSUB/ 내 모든 테스트 케이스가 올바르게 작동하지만 잘못된 답변을 얻고 있습니다. 나는 코드를 많이 바꾸려고했으나 여전히 WA가 있습니다. 메신저가 오버플로를 방지하기 위해 합계를 추가 할 때 나는 mod를 취하고 있습니다. 그럴까요?

> my algorithm: 
> sum of all +ve num will be the maximum sum. 
> if there is no +ve number after sorting take the last element as the max number. 
> case 1: last element is -ve. 
>  number of subsets=number of times it occurs 
> case 2: last element is 0. 
>  cnt=number of 0's. 
>  number of subsets=2^cnt-1(excluding the null set) 

아무도 도와 줄 수 있습니까 ??

#include<iostream> 
#include<cstdio> 
#include<deque> 
#include<algorithm> 
#include<math.h> 

#define MOD 1000000009 


using namespace std; 
typedef long long int L; 
int main(){ 
int t; 
L n; 
scanf("%d",&t); 
while(t--){ 
    scanf("%lld",&n); 
    L arr[51000],sum=0LL; 
    L cnt=1LL; 

    for(int i=0;i<n;i++){ 
     scanf("%lld",&arr[i]); 
     if(arr[i]>0){ 
      sum+=(long long)arr[i]; 
      sum%=MOD; 
     // f=1; 
     } 
    } 
     sort(arr,arr+n); 
     if(sum==0){//this is to check if there is no +ve num 
      sum=arr[n-1]; 
      for(int j=n-2;j>=0;j--){ 
       if(sum==arr[j]) 
        cnt++; 
       else 
        break; 
      } 
      if(sum==0){//this is to check if the maximum num is 0 
       L num=1; 
       for(int k=0;k<cnt;k++){ 
        num=(L)(num*2)%MOD;//if sum==0 then num of subset is 2^cnt-1 
       }//decrementing 1 from 2^cnt coz we do not include null set 
       cnt=num-1; 
       } 
      } 
      cnt=cnt%MOD; 
    printf("%lld %lld\n",sum,cnt); 
} 

}

Answer 1

내가 라인으로 코드 라인을 읽어 보지 않았,하지만 난 당신이 적어도 하나의 사건을 놓친 생각 -

입력에 모두 긍정적 인 숫자 1과 0이 될 수있는 이 경우 응답은 2^(# of zeros)이어야합니다.