Problem:


Score : 600 points

Problem Statement

You are given N integers. The i-th integer is a_i.
Find the number, modulo 998244353, of ways to paint each of the integers red, green or blue so that the following condition is satisfied:

Let R, G and B be the sums of the integers painted red, green and blue, respectively. There exists a triangle with positive area whose sides have lengths R, G and B.

Constraints

3 \leq N \leq 300

1 \leq a_i \leq 300(1\leq i\leq N)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1
:
a_N

Output

Print the number, modulo 998244353, of ways to paint each of the integers red, green or blue so that the condition is satisfied.

Sample Input 1

4
1
1
1
2

Sample Output 1

18

We can only paint the integers so that the lengths of the sides of the triangle will be 1, 2 and 2, and there are 18 such ways.

Sample Input 2

6
1
3
2
3
5
2

Sample Output 2

150

Sample Input 3

20
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9
3
2
3
8
4

Sample Output 3

563038556



Sample input:
4
1
1
1
2


Sample output:
18

Submission status: Runtime Error

Solution code:
	if r > total_val/2:
		return 0
	
	if r + rest_vals[i] < total_val/2:
		return 0
	
	if (i,r) in ans_dict_eq_2.keys():
		return ans_dict_eq_2[(i,r)]
	

	ret = calc_eq_2(i+1,r+vals[i]) + calc_eq_2(i+1,r)
	ans_dict_eq_2[(i,r)] = ret
	return ret

if total_val % 2 == 0:
	ptn_num = 3 ** N - 3*(calc_bigger(0,0) - calc_eq_2(0,0))
else:
	ptn_num = 3 ** N - 3*(calc_bigger(0,0))

print(ptn_num % 998244353)

Submission status: Runtime Error

Solution code:
# D
N = int(input())
a_list = [0]*N
for i in range(N):
    a_list[i] = int(input())

L = 90001
LARGE = 998244353

DP = np.zeros(L, dtype="int")
DP[0] = 1
for i in range(N):
    for j in range(L-1, a_list[i]-1, -1):
        DP[j] = (2*DP[j] + DP[j - a_list[i]]) % LARGE
    for j in range(a_list[i]-1, -1, -1):
        DP[j] = (2*DP[j]) % LARGE

DP2 = np.zeros(L, dtype="int")
DP2[0] = 1
for i in range(N):
    for j in range(L-1, a_list[i]-1, -1):
        DP2[j] = (DP2[j] + DP2[j - a_list[i]]) % LARGE
    for j in range(a_list[i]-1, -1, -1):
        DP2[j] = (DP2[j]) % LARGE
S = sum(a_list)
if S % 2 == 0:
    h = S // 2
    res = ((3**N % LARGE) - (3*sum(DP[(h):]) % LARGE) + 3*DP2[h]) % LARGE
else:
    h = S // 2 + 1
    res = ((3**N % LARGE) - (3*sum(DP[(h):]) % LARGE)) % LARGE
print(res)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [abs(int(input())) for _ in range(N)]
#A.sort()
s = sum(A)

def mulmod(p,q,mod):
  return ((p%mod)*(q%mod))%mod
def powermod(p,n,mod):
  if n==0: return 1
  if n==1: return p%mod
  else:    return powermod(p,n//2,mod)**2 * (p**(n%2)) %mod
def dividemod(p,q,mod):
  # modは素数
  return mulmod(p, powermod(q,mod-2,mod), mod)

mod = 998244353

import numpy as np

dp = [np.zeros(s+1) for _ in range(N)]


# dp[n][s] An-1(0-index)まで加えて、Rの和がsになるのが何通りか（残りのG,Bまで含めて）
dp[0][0] = 2
dp[0][A[0]] = 1
temp_sum = A[0]

for i in range(1,N):
  dp[i] = np.mod((np.roll(dp[i-1], A[i]) + dp[i-1]*2), mod)
  temp_sum += A[i]

def part_sum(a,A):
  p=mod
  #初期化
  N=len(a)
  dp=[[0 for i in range(A+1)] for j in range(N+1)]
  dp[0][0]=1

  #DP
  for i in range(N):
    for j in range(A+1):
      if a[i]<=j: #i+1番目の数字a[i]を足せるかも
        dp[i+1][j]=dp[i][j-a[i]]+ dp[i][j]% p
      else: #入る可能性はない
        dp[i+1][j]=dp[i][j]%p
  return dp[N][A]

ps = part_sum(A, s//2)

if s%2 != 0:
    answer = (powermod(3, N, mod) - 3*sum(dp[N-1][(s+1)//2:]))%mod
else:
    answer = (powermod(3, N, mod) - 3*(sum(dp[N-1][(s+1)//2:]) - ps))%mod

answer = int(answer)

print(answer)

Submission status: Runtime Error

Solution code:
import math
import copy


def trial_division(n):
    factor = []
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor.append(num)

    if not factor:
        return set([])
    else:
        factor.append(n)
        return set(factor)


def solve():
    n = int(input())
    a = []
    for i in range(n + 1):
        a.append(int(input()))

    primes = trial_division(a[-1])

    for e in a[:-1]:
        output = copy.deepcopy(primes)
        for p in primes:
            if p % e != 0:
                output.remove(p)
    for p in primes:
        print(p)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  int w = 17;
  vector<vector<int>> data(w, vector<int>(w,0));
  vector<vector<int>> newdata(w,vector<int>(w,0));
  data[0][0] = 1;
  int sm = 0;
  for (int i = 0;i < n;i++){
    int ai;
    cin >> ai;
    sm += ai;
    newdata = data;
    for (int j = 0;j < w;j++){
      for (int k = 0;k < w;k++){
        if (ai+j < w){
          newdata[ai+j][k] += data[j][k];
        }
        if (ai+k < w){
          newdata[j][ai+k] += data[j][k];
        }
      }
    }
    data = newdata;
  }
  int c = 0;
  for (int j = 0;j < w;j++){
      for (int k = 0;k < w;k++){
        int r = j;
        int g = k;
        int b = sm -j -k;
        int m = max({r,g,b});
        if (2*m < r+g+b) {
          c = (c + newdata[j][k])%998244353;
        }
      }
  }
  cout  << c << endl;
}

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
mod = 998244353
n = int(input())
a = [int(input()) for i in range(n)]
d = max(a)
dp = [[[0]*(d*n+1) for i in range(d*n+1)] for j in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(d*n+1-d):
        for k in range(d*n+1-d):
            dp[i+1][j+a[i]][k] += dp[i][j][k]
            dp[i+1][j][k+a[i]] += dp[i][j][k]
            dp[i+1][j][k] += dp[i][j][k]
            dp[i+1][j+a[i]][k] %= mod
            dp[i+1][j][k+a[i]] %= mod
            dp[i+1][j][k] %= mod
go = sum(a)
ans = 0
for j in range(1,d*n+1):
    for k in range(1,d*n+1):
        if dp[n][j][k]:
            side1 = j
            side2 = k
            side3 = go-j-k
            if side3 == 0:
                continue
            if(side1+side2>side3)and(side2+side3>side1)and(side3+side1>side2):
                ans += dp[n][j][k]
                ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
LEN = 300

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

dp = [[[0 for i in range(LEN)] for j in range(LEN)] for k in range(LEN)]
dp[0][0][0] = 1

s = 0
for a in A:
    for i in range(s+1):
        for j in range(s+1-i):
            k = s - i - j
            dp[i+a][j][k] += dp[i][j][k]
            dp[i][j+a][k] += dp[i][j][k]
            dp[i][j][k+a] += dp[i][j][k]
    s += a

res = 0
for i in range(1, LEN):
    for j in range(1, LEN):
        k = s - i - j
        if k>0 and i+j>k and j+k>i and k+i>j:
            res += dp[i][j][k]
print(res%998244353)

Submission status: Runtime Error

Solution code:
LEN = 100

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

dp = [[[0 for i in range(LEN)] for j in range(LEN)] for k in range(LEN)]
dp[0][0][0] = 1

s = 0
for a in A:
    for i in range(s+1):
        for j in range(s+1-i):
            k = s - i - j
            dp[i+a][j][k] += dp[i][j][k]
            dp[i][j+a][k] += dp[i][j][k]
            dp[i][j][k+a] += dp[i][j][k]
    s += a

res = 0
for i in range(1, LEN):
    for j in range(1, LEN):
        k = s - i - j
        if k>0 and i+j>k and j+k>i and k+i>j:
            res += dp[i][j][k]
print(res%998244353)

Submission status: Runtime Error

Solution code:
N=int(input())
A=[int(input()) for i in range(N)]
S=sum(A)
mod=998244353
dp=[[[0]*(S//2+1) for i in range(S//2+1)] for i in range(N+1)]
dp[0][0][0]=1
for i in range(N):
  for r in range(S//2+1):
    for b in range(S//2+1):
      dp[i+1][r][b]=dp[i][r][b]
      if r-A[i]>=0:
        dp[i+1][r][b]+=dp[i][r-A[i]][b]
      if b-A[i]>=0:
        dp[i+1][r][b]+=dp[i][r][b-A[i]]
      dp[i+1][r][b]%=mod
ans=0     
for r in range(S//2+1):
  for b in range(S//2+1):
    if r+b>S/2 and r<S/2 and b<S/2:
      ans+=dp[N][r][b]
      ans%=mod
print(ans)