Submission #00132

ソースコード

#include<bits/stdc++.h>
using namespace std;
int n,a[100];
long long int f(int idx,int sum);
long long int memo[100][21];
main(){
  memset(memo,-1,sizeof(memo));
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  cout<<f(1,a[0])<<endl;
}
long long int f(int idx,int sum){
  long long int ret=0;
  if(idx==n-1){
    if(sum==a[n-1])return 1;
    else return 0;
  }
  if(memo[idx][sum]!=-1)return memo[idx][sum];
  sum+=a[idx];
  if(sum>=0 && sum<=20)ret+=f(idx+1,sum);
  sum-=a[idx]*2;
  if(sum>=0 && sum<=20)ret+=f(idx+1,sum);
  return memo[idx][sum+a[idx]]=ret;
}

ステータス

項目	データ
問題	0004 - 1年生 (A First Grader)
ユーザー名	ei1516
投稿日時	2016-11-09 18:52:49
言語	C++11
状態	Accepted
得点	100
ソースコード長	594 Byte
最大実行時間	21 ms
最大メモリ使用量	568 KB

セット

	セット	得点	Cases
1	入力1	20 / 20	*1.txt
2	入力2	20 / 20	*2.txt
3	入力3	20 / 20	*3.txt
4	入力4	20 / 20	*4.txt
5	入力5	20 / 20	*5.txt

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
2011-yo-t4-in1.txt	AC	19 ms	480 KB	1
2011-yo-t4-in2.txt	AC	17 ms	568 KB		2
2011-yo-t4-in3.txt	AC	21 ms	412 KB			3
2011-yo-t4-in4.txt	AC	19 ms	380 KB				4
2011-yo-t4-in5.txt	AC	19 ms	476 KB					5