結果
問題 | No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木 |
ユーザー |
![]() |
提出日時 | 2021-12-09 16:41:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 245 ms / 2,000 ms |
コード長 | 1,661 bytes |
コンパイル時間 | 3,956 ms |
コンパイル使用メモリ | 259,096 KB |
最終ジャッジ日時 | 2025-01-26 07:16:20 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint1000000007; using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) #define Inf 100000000000000001 int main(){ vector<int> C(26); rep(i,26){ cin>>C[i]; C[i]--; } vector<int> K(26); rep(i,26)cin>>K[i]; vector dp(26,vector(30,vector(16,vector<long long>(16,-Inf)))); { int N; cin>>N; rep(i,N){ string S; cin>>S; long long A,B,E; cin>>A>>B>>E; A--;B--; rep(j,S.size()){ dp[S[j]-'A'][0][A][B] = max(dp[S[j]-'A'][0][A][B], E); dp[S[j]-'A'][0][B][A] = max(dp[S[j]-'A'][0][B][A], E); } } rep(i,26){ rep(j,16){ dp[i][0][j][j] = 0LL; } } } rep(i,26){ for(int j=1;j<30;j++){ rep(k,16){ rep(l,16){ rep(m,16){ long long X = dp[i][j-1][k][l],Y = dp[i][j-1][l][m]; if(X==-Inf||Y==-Inf)continue; dp[i][j][k][m] = max(dp[i][j][k][m],X+Y); } } } } } vector<vector<long long>> cost(26); rep(i,26){ vector<long long> cur(16,-Inf); cur[C[i]] = 0LL; rep(j,30){ if(K[i]&1){ vector<long long> nc(16,-Inf); rep(k,16){ rep(l,16){ long long X = cur[k]; long long Y= dp[i][j][k][l]; if(X==-Inf||Y==-Inf)continue; nc[l] = max(nc[l],X+Y); } } swap(cur,nc); } K[i]>>=1; } cost[i] = cur; } long long ans = -Inf; rep(i,16){ long long sum = 0LL; rep(j,26){ long long t = cost[j][i]; if(t==-Inf){ sum = -Inf; break; } sum += t; } ans = max(ans,sum); } if(ans==-Inf)cout<<"Impossible"<<endl; else cout<<ans<<endl; return 0; }