結果
問題 |
No.1845 Long Substrings
|
ユーザー |
|
提出日時 | 2022-02-19 19:33:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 756 bytes |
コンパイル時間 | 1,992 ms |
コンパイル使用メモリ | 193,332 KB |
最終ジャッジ日時 | 2025-01-28 01:03:46 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 WA * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main () { int N; cin >> N; ll num[200010]; for (int i = 0; i < N; i ++) { cin >> num[i]; } string s; cin >> s; int id[26]; ll dp[26]; for (int i = 0; i < 26; i ++) { id[i] = -1; dp[i] = 0; } id[s[0] - 'a'] = 0; dp[s[0] - 'a'] = 1; ll m = 1e9 + 7; ll ans = num[0]; for (int i = 1; i < N; i ++) { int n = s[i] - 'a'; for (int j = 0; j < 26; j ++) { if (j != n && id[j] > id[n]) { dp[n] += dp[j]; dp[n] %= m; } } id[n] = i; ans += (dp[n] * num[i]) % m; ans %= m; } cout << ans << endl; }