結果
問題 | No.2310 [Cherry 5th Tune A] Against Regret |
ユーザー |
👑 ![]() |
提出日時 | 2023-02-27 21:51:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,405 ms / 6,000 ms |
コード長 | 1,256 bytes |
コンパイル時間 | 293 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 81,068 KB |
最終ジャッジ日時 | 2024-09-15 21:49:14 |
合計ジャッジ時間 | 37,609 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
def solve():N=int(input())X=[None]*(N+1)for u in range(N+1):X[u]=list(map(int,input().split()))Mod=998244353# 前計算S=[[0]*(N+1) for _ in range(N+1)]for u in range(N+1):Su=S[u]Su[u]=1for v in range(u,N+1):Xv=X[v]for w in range(v+1,N+1):Su[w]+=Su[v]*Xv[w]Su[w]%=ModQ=int(input())Ans=[0]*Qfor q in range(Q):K=int(input())A=[0]*K; B=[0]*K; C=[0]*KV=[]for k in range(K):A[k],B[k],C[k]=map(int,input().split())V.append((A[k],1,k))V.append((B[k],0,k))Ans[q]=S[0][N]DPa=[S[0][A[k]] for k in range(K)]DPb=[0]*KV.sort()for v,t,k in V:if t==1:DPb[k]+=DPa[k]*C[k]DPb[k]%=Modelse:Ans[q]+=DPb[k]*S[B[k]][N]Ans[q]%=Modfor l in range(K):DPa[l]+=DPb[k]*S[B[k]][A[l]]DPa[l]%=Modreturn Ans#==================================================import sysinput=sys.stdin.readlinewrite=sys.stdout.writewrite("\n".join(map(str,solve())))