結果
問題 | No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木 |
ユーザー |
👑 ![]() |
提出日時 | 2021-12-09 00:21:36 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 139 ms / 2,000 ms |
コード長 | 2,074 bytes |
コンパイル時間 | 2,829 ms |
コンパイル使用メモリ | 113,356 KB |
最終ジャッジ日時 | 2025-01-26 07:00:00 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>using namespace std;using i32 = int32_t;using u32 = uint32_t;using i64 = int64_t;using u64 = uint64_t;#define rep(i,n) for(int i=0; i<(n); i++)string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";i64 C[26];i64 K[26];int N;vector<string> S;vector<int> A;vector<int> B;vector<i64> E;i64 G[64][16][16];i64 ans[16];int main() {rep(i,26){ cin >> C[i]; C[i]--; }rep(i,26) cin >> K[i];cin >> N;S.resize(N);A.resize(N);B.resize(N);E.resize(N);rep(i,N){ cin >> S[i] >> A[i] >> B[i] >> E[i]; A[i]--; B[i]--; }const i64 INF = 1001001001001001001;rep(a,16) ans[a] = 0;rep(i,26){rep(d,64) rep(a,16) rep(b,16) G[d][a][b] = -INF;rep(d,64) rep(a,16) G[d][a][a] = 0;rep(n,N) if(S[n].find(ALPHABET[i]) != string::npos){int a = A[n], b = B[n];G[0][a][b] = max(G[0][a][b], E[n]);G[0][b][a] = max(G[0][b][a], E[n]);}rep(d,63) rep(a,16) rep(b,16) rep(c,16) G[d+1][a][c] = max(G[d+1][a][c], G[d][a][b] + G[d][b][c]);//rep(a,16){ rep(b,16) cout << G[0][a][b] << " "; cout << endl; } cout << endl;i64 vec[16];rep(a,16) vec[a] = -INF;vec[C[i]] = 0;for(int d=30; d>=0; d--) if(1 & (K[i] >> d)){//cout << "d = " << d << endl;i64 vecbuf[16];rep(a,16) vecbuf[a] = vec[a];rep(a,16) rep(b,16) vecbuf[b] = max(vecbuf[b], vec[a] + G[d][a][b]);rep(a,16) vec[a] = vecbuf[a];}//for(auto a : vec) cout << a << " "; cout << endl;rep(a,16){ans[a] += vec[a];ans[a] = max(ans[a], -INF);}}i64 finalans = -INF;rep(a,16) finalans = max(finalans, ans[a]);if(-INF / 10 < finalans) cout << finalans << endl;else cout << "Impossible" << endl;return 0;}struct ios_do_not_sync{ios_do_not_sync(){ios::sync_with_stdio(false);cin.tie(nullptr);}} ios_do_not_sync_instance;