i didnt use many optimization ... only used Memorization (Using STL map )...
also Calculated the result for i:0...10^6 using incremental method ... it tool 4s To calculate FOR 10^6
but FOR this Test Case
2
750 749
999999999999999
it took minutes to complete ...
so i didnt try much other minor optimizations like reducing number of * or % ...
There should be other method to solve this Test Case ...
100
750 749 748 747 746 745 744 743 742 741 740 739 738 737 736 735 734 733 732 731
730 729 728 727 726 725 724 723 722 721 720 719 718 717 716 715 714 713 712 711
710 709 708 707 706 705 704 703 702 701 700 699 698 697 696 695 694 693 692 691
690 689 688 687 686 685 684 683 682 681 680 679 678 677 676 675 674 673 672 671
670 669 668 667 666 665 664 663 662 661 660 659 658 657 656 655 654 653 652 651
999999999999999
one other possible optimization could be to avoid computing for same block sizes and just calculate distinct sizes ...
but it would not work in worst Case ....
in Rank list There are ACs below 2s ...
i wonder whats the Right approach !!
Code: Select all
#include<iostream>
#include<algorithm>
#include<map>
#include<ctime>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;++i)
map<long long ,long long> DP;
long long memorize[1000000];
const long long Mode= 100000007;
int in[128],n;
long long Find(long long range){
//printf("%lld\n",range);
if(DP.count(range) )return DP[range];
long long res=0;
FOR(i,n){
if(in[i]>range)continue;
else if(in[i]==range)res+=1;
else {
FOR( r,in[i] ){
long long a= range/2-in[i]+r+1,
b= range-(range/2+r)-1;
//printf("%lld %lld %lld\n",a,b,range );
if(a<0 || b<0)continue;
res= ( res+(Find(a)*Find(b)) )%Mode;
}
}
}
return ( DP[range]=res%Mode );
}
int main(){
//FOR(i,100)printf("%d ",750-i );
freopen("in.txt","r",stdin);
int cas;
scanf("%d",&cas);
FOR(ca,cas){
DP.clear();
scanf("%d",&n);
int mini=214778;
FOR(i,n){
scanf("%d",&in[i] );
mini=min(mini,in[i] );
}
FOR(i,mini) DP[i]=memorize[i]=0;
DP[0]=memorize[0]=1;
long long range;
scanf("%lld",&range);
//long long start=clock();
int Max=min<long long>(1000000,range+1 );
for(int i=mini;i<Max;++i){
memorize[i]=0;
FOR(j,n)if(in[j]<=i)memorize[i]+=memorize[ i-in[j] ];
memorize[i]%=Mode;
DP[i]=memorize[i];
}
//printf("PreTime : %lld\n",clock()-start );
//start=clock();
long long res=Find(range);
//long long end=clock();
pr//intf("Time : %lld\n",end-start );
printf("Case %d: %lld\n",ca+1,res);
//break;
}
return 0;
}