i think this wl work.
#include<cstdio>
long long int myread()
{
char str[20];
long long int sum,i;
scanf("%s",str);
for(i=0,sum=0;str[i];i++)
sum =(sum*10)+str[i]-'0';
return sum;
}
long long arr[50020];
#define MOD 1000000009LL
long long modulo(int a,long long b) {
long long x=1,y=a;
while(b) { if((b&1)==1) x=(x*y)%MOD;y=(y*y)%MOD;b>>=1;}
return x;
}
int main() {
int test,c,pc;
test=myread();
long long n,num,maxsum,cnt;
while(test--) {n=myread();
maxsum=-1000000001,c=0,pc=0,cnt=0;
int index=-1;
for(int i=0;i<n;i++) {
scanf("%lld",&num);arr[++index]=num;
if(num>0){if(maxsum<0) maxsum=0;maxsum+=num,pc++;}
else if(num<0) { if(num>maxsum) maxsum=num;}
else if(num==0) {if(num>maxsum) maxsum=num;c++;}
}
long long mod=modulo(2,c);
printf("%lld",maxsum);
if(pc>0) cnt=mod;
else if(c>0&&c!=n) {cnt=mod-1;}
else { if(c==n) cnt=mod-1; else {c=0;for(int
i=0;i<=index;i++)
if(arr[i]==maxsum)c++; cnt=c;}}
printf(" %lld\n",cnt);
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
