結果
問題 | No.1555 Constructed Balancing Sequence |
ユーザー |
|
提出日時 | 2021-01-04 03:13:35 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,683 bytes |
コンパイル時間 | 213 ms |
コンパイル使用メモリ | 82,140 KB |
実行使用メモリ | 766,920 KB |
最終ジャッジ日時 | 2024-06-22 19:26:41 |
合計ジャッジ時間 | 4,781 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 MLE * 1 |
other | -- * 42 |
ソースコード
def solve(N,K,A):diff = [A[0] for i in range(N)]S = A[0]for i in range(1,N):diff[i] = S - A[i]if diff[i] < 0:return 0S += A[i]diff.append(0)dp = [{} for i in range(N-1)]stack = [(N-2,dp_S) for dp_S in range(10*K+10)]while stack:i,j = stack.pop()if j in dp[i]:continuedp[i][j] = [0 for k in range(6*K+2)]if not i:continueif diff[i]:stack.append((i-1,(j+diff[i+1]-2*K-1+diff[i])//2-diff[i]+2*K+1))if diff[i]<=1:for k in range(-2,1):stack.append((i-1,(j+diff[i+1]-2*K-1+k)//2+2*K+1))stack.append((i-1,(j+diff[i+1]-2*K-1-diff[i])//2+2*K+1))cum = [{sum:[0 for minus in range(6*K+2)] for sum in dp[i]} for i in range(N-1)]mod = 998244353for minus in range(6*K+2):for sum in dp[0]:dp_S = sum - minusreal_S = diff[1] + dp_S - 2*K - 1first = diff[0] - minusif first==real_S and -K<=first<=K:dp[0][sum][minus] = 1for sum in dp[0]:cum[0][sum][0] = dp[0][sum][0]for minus in range(1,6*K+2):cum[0][sum][minus] = dp[0][sum][minus] + cum[0][sum][minus-1]cum[0][sum][minus] %= modfor i in range(1,N-1):for minus in range(6*K+2):for sum in dp[i]:dp_S = sum - minusreal_S = dp_S + diff[i+1] - 2*K - 1if diff[i]:L = max((real_S+minus+diff[i]+1)//2,-K+minus+diff[i])R = min((real_S+minus+diff[i])//2,K+minus+diff[i])if L==R:pre_dp_S = L - diff[i] + 2*K + 1dp[i][sum][minus] += dp[i-1][pre_dp_S][0]dp[i][sum][minus] %= modif minus%2==diff[i] and real_S%2==0 and -K<=real_S//2<=K:pre_minus_L = max(0,minus//2+1+diff[i])pre_minus_R = min(6*K+1,minus//2+3*K+diff[i])if pre_minus_L<=pre_minus_R:pre_sum = real_S//2+minus//2+2*K+1dp[i][sum][minus] += cum[i-1][pre_sum][pre_minus_R] - cum[i-1][pre_sum][pre_minus_L] + dp[i-1][pre_sum][pre_minus_L]dp[i][sum][minus] %= modif diff[i]<=1 and (real_S+minus-diff[i])%2==0:m = max(0,-K+minus-diff[i]-(real_S+minus-diff[i])//2)M = min((minus-diff[i])//2,K+minus-diff[i]-(real_S+minus-diff[i])//2)pre_minus_L = max(0,m+diff[i])pre_minus_R = min(6*K+1,M+diff[i])if pre_minus_R>=pre_minus_L:pre_sum = (real_S+minus-diff[i])//2+2*K+1dp[i][sum][minus] += cum[i-1][pre_sum][pre_minus_R] - cum[i-1][pre_sum][pre_minus_L] + dp[i-1][pre_sum][pre_minus_L]dp[i][sum][minus] %= modfor sum in cum[i]:cum[i][sum][0] = dp[i][sum][0]for minus in range(1,6*K+2):cum[i][sum][minus] = cum[i][sum][minus-1] + dp[i][sum][minus]cum[i][sum][minus] %= modres = 0for real_S in range(-N*K,N*K+1):minus = 0i = N - 1if diff[i]:L = max((real_S+minus+diff[i]+1)//2,-K+minus+diff[i])R = min((real_S+minus+diff[i])//2,K+minus+diff[i])if L==R:pre_dp_S = L - diff[i] + 2*K + 1res += dp[i-1][pre_dp_S][0]res %= modif minus%2==diff[i] and real_S%2==0 and -K<=real_S//2<=K:pre_minus_L = max(0,minus//2+1+diff[i])pre_minus_R = min(6*K+1,minus//2+3*K+diff[i])if pre_minus_L<=pre_minus_R:pre_sum = real_S//2+minus//2+2*K+1res += cum[i-1][pre_sum][pre_minus_R] - cum[i-1][pre_sum][pre_minus_L] + dp[i-1][pre_sum][pre_minus_L]res %= modif diff[i]<=1 and (real_S+minus-diff[i])%2==0:m = max(0,-K+minus-diff[i]-(real_S+minus-diff[i])//2)M = min((minus-diff[i])//2,K+minus-diff[i]-(real_S+minus-diff[i])//2)pre_minus_L = max(0,m+diff[i])pre_minus_R = min(6*K+1,M+diff[i])if pre_minus_R>=pre_minus_L:pre_sum = (real_S+minus-diff[i])//2+2*K+1res += cum[i-1][pre_sum][pre_minus_R] - cum[i-1][pre_sum][pre_minus_L] + dp[i-1][pre_sum][pre_minus_L]res %= modreturn resN,K = map(int,input().split())A = list(map(int,input().split()))print(solve(N,K,A))