MAXIMAL SUBSET OF ARRAY

gistfile1.cpp

#include <algorithm>
#include <math.h>
#include <numeric>
#include <iostream>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <cstring>
#define lli long long int
#define MOD 1000000009
using namespace std;
long long int precalculo[60000];
lli t, n, maximo;
int main(){
     scanf("%lld", &t);
     long long int power =1;
     for(int i=1 ; i <= 50300; i++){
         power=(power * 2)%MOD;
         precalculo[i] = power;
     }
     while(t--){
     scanf("%lld", &n);
         lli A[n+5];
         lli zeros= 0;
         lli appear  = 0 ;
         maximo = -99999;
         lli mas = 0;
         for(lli i =0 ; i < n; i++){
             scanf("%lld", &A[i]);
             if(A[i]==0)zeros++;
             maximo = max(maximo, A[i]);
         }
        sort(A, A+n);
        if(maximo == 0){
             cout << 0 <<" "<< ((precalculo[zeros])-1 + MOD ) % MOD<<endl;   
        }
        lli acumulado = 0;
         if(maximo > 0){
             lli  i = n-1;
             while(A[i]>0&& i>=0 ){
                     appear++;
                     acumulado+=A[i];
                     i--;
             }            
             n = appear+zeros;
             if(zeros)cout << acumulado << " "<<(precalculo[zeros])<<endl;
             else            cout << acumulado << " "<<1<<endl;
         }
         if(maximo < 0 ){
           appear = 1;
           lli  i = n-1;
           while(A[i]==A[i-1]&&i>0){
               appear++;
               i--;
           }
           cout << A[n-1]<<" "<<appear%MOD<<endl;
       
         }
     }
    return 0;
}