結果
問題 | No.2310 [Cherry 5th Tune A] Against Regret |
ユーザー | kotatsugame |
提出日時 | 2023-05-19 22:23:35 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,269 ms / 6,000 ms |
コード長 | 1,615 bytes |
コンパイル時間 | 1,129 ms |
コンパイル使用メモリ | 81,040 KB |
実行使用メモリ | 4,940 KB |
最終ジャッジ日時 | 2023-08-23 00:18:03 |
合計ジャッジ時間 | 22,583 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,612 KB |
testcase_01 | AC | 3 ms
4,676 KB |
testcase_02 | AC | 3 ms
4,628 KB |
testcase_03 | AC | 5 ms
4,676 KB |
testcase_04 | AC | 5 ms
4,640 KB |
testcase_05 | AC | 5 ms
4,912 KB |
testcase_06 | AC | 4 ms
4,704 KB |
testcase_07 | AC | 4 ms
4,684 KB |
testcase_08 | AC | 110 ms
4,624 KB |
testcase_09 | AC | 206 ms
4,640 KB |
testcase_10 | AC | 291 ms
4,640 KB |
testcase_11 | AC | 466 ms
4,700 KB |
testcase_12 | AC | 431 ms
4,732 KB |
testcase_13 | AC | 222 ms
4,680 KB |
testcase_14 | AC | 270 ms
4,732 KB |
testcase_15 | AC | 520 ms
4,652 KB |
testcase_16 | AC | 54 ms
4,648 KB |
testcase_17 | AC | 260 ms
4,672 KB |
testcase_18 | AC | 1,267 ms
4,828 KB |
testcase_19 | AC | 1,268 ms
4,696 KB |
testcase_20 | AC | 1,266 ms
4,636 KB |
testcase_21 | AC | 1,262 ms
4,624 KB |
testcase_22 | AC | 1,265 ms
4,940 KB |
testcase_23 | AC | 1,264 ms
4,676 KB |
testcase_24 | AC | 1,269 ms
4,684 KB |
testcase_25 | AC | 1,269 ms
4,668 KB |
testcase_26 | AC | 1,264 ms
4,640 KB |
testcase_27 | AC | 1,265 ms
4,688 KB |
testcase_28 | AC | 1,247 ms
4,824 KB |
testcase_29 | AC | 705 ms
4,600 KB |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<atcoder/modint> using namespace std; using mint=atcoder::modint998244353; int N; mint dp[401][401]; mint X[401][401]; mint ep[401]; mint fp[62][2]; mint M[62][62],M2[62][62]; int K; int A[30],B[30]; mint C[30]; int main() { cin>>N; for(int i=0;i<=N;i++)for(int j=0;j<=N;j++) { int x;cin>>x; if(x==998244353)X[i][j]=mint::raw(0); else X[i][j]=mint::raw(x); } for(int s=0;s<N;s++) { for(int i=s;i<=N;i++)ep[i]=mint::raw(0); ep[s]=mint::raw(1); for(int i=s;i<N;i++)for(int j=i+1;j<=N;j++)ep[j]+=ep[i]*X[i][j]; for(int t=s+1;t<=N;t++)dp[s][t]=ep[t]; } int Q;cin>>Q; vector<int>vs; vs.reserve(62); for(;Q--;) { cin>>K; vs.clear(); vs.push_back(0); vs.push_back(N); for(int i=0;i<K;i++) { cin>>A[i]>>B[i]; vs.push_back(A[i]); vs.push_back(B[i]); int c;cin>>c; if(c==998244353)C[i]=mint::raw(0); else C[i]=mint::raw(c); } sort(vs.begin(),vs.end()); vs.erase(unique(vs.begin(),vs.end()),vs.end()); for(int i=0;i<vs.size();i++)for(int j=0;j<vs.size();j++) { M[i][j]=dp[vs[i]][vs[j]]; M2[i][j]=mint::raw(0); } for(int i=0;i<K;i++) { int a=lower_bound(vs.begin(),vs.end(),A[i])-vs.begin(); int b=lower_bound(vs.begin(),vs.end(),B[i])-vs.begin(); M2[a][b]+=C[i]; } for(int i=0;i<vs.size();i++) { fp[i][0]=fp[i][1]=mint::raw(0); } fp[0][1]=mint::raw(1); for(int i=0;i<vs.size();i++)for(int j=i+1;j<vs.size();j++) { fp[j][0]+=fp[i][1]*M[i][j]; fp[j][1]+=(fp[i][0]+fp[i][1])*M2[i][j]; } cout<<(fp[vs.size()-1][0]+fp[vs.size()-1][1]).val()<<"\n"; } }