結果
問題 | No.1029 JJOOII 3 |
ユーザー | Rho |
提出日時 | 2020-04-16 20:34:55 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,926 bytes |
コンパイル時間 | 2,193 ms |
コンパイル使用メモリ | 167,396 KB |
実行使用メモリ | 194,044 KB |
最終ジャッジ日時 | 2024-04-10 07:03:19 |
合計ジャッジ時間 | 6,166 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 7 ms
17,344 KB |
testcase_01 | AC | 1 ms
6,940 KB |
testcase_02 | AC | 10 ms
23,288 KB |
testcase_03 | AC | 29 ms
57,368 KB |
testcase_04 | AC | 28 ms
58,796 KB |
testcase_05 | AC | 115 ms
191,980 KB |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | AC | 109 ms
189,056 KB |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | AC | 111 ms
186,900 KB |
testcase_13 | AC | 110 ms
189,308 KB |
testcase_14 | WA | - |
testcase_15 | AC | 2 ms
6,940 KB |
testcase_16 | AC | 2 ms
6,944 KB |
testcase_17 | AC | 2 ms
6,940 KB |
testcase_18 | AC | 108 ms
184,628 KB |
testcase_19 | AC | 11 ms
20,820 KB |
testcase_20 | WA | - |
testcase_21 | AC | 74 ms
127,604 KB |
testcase_22 | AC | 77 ms
127,520 KB |
testcase_23 | AC | 74 ms
129,332 KB |
testcase_24 | AC | 74 ms
127,520 KB |
testcase_25 | AC | 79 ms
132,780 KB |
testcase_26 | AC | 106 ms
176,864 KB |
testcase_27 | AC | 118 ms
186,860 KB |
testcase_28 | AC | 113 ms
185,540 KB |
testcase_29 | AC | 108 ms
183,848 KB |
testcase_30 | WA | - |
testcase_31 | AC | 112 ms
182,892 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | AC | 175 ms
194,044 KB |
testcase_36 | WA | - |
testcase_37 | AC | 6 ms
12,168 KB |
testcase_38 | WA | - |
testcase_39 | AC | 8 ms
20,252 KB |
testcase_40 | AC | 7 ms
19,388 KB |
ソースコード
#include"bits/stdc++.h" using namespace std; #define int long long #define rep(i,n) for(int i=0;i<n;i++) string s[82]; int c[82];int n, K; int l[3][82]; int dp[3][83][100200];//dp[文字i][j種類][今k文字] int rwa[3][82][82]; void memo() { rep(i, 3)rep(j, n + 1)rep(k, 100200)dp[i][j][k] = 1e15; rep(i, 3) { dp[i][0][0] = 0; rep(j, n) { rep(k, 100105) { dp[i][j + 1][k] = min(dp[i][j][k], dp[i][j + 1][k]); if(k>=l[i][j])dp[i][j + 1][k] = min(dp[i][j + 1][k], dp[i][j+1][k-l[i][j]] + c[j]); } } rep(k, 100100)dp[i][n][k] = min(dp[i][n][k], dp[i][n][k + 1]); } } signed main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n >> K; int ej = 0, eo = 0, ei = 0; rep(i, n) { cin >> s[i] >> c[i]; rep(j, s[i].size()) { if (s[i][j] == 'J') { l[0][i]++; rwa[0][i][j + 1]++; } if (s[i][j] == 'O') { l[1][i]++; rwa[1][i][j + 1]++; } if (s[i][j] == 'I') { l[2][i]++; rwa[2][i][j + 1]++; } } ej += l[0][i]; eo += l[1][i]; ei += l[2][i]; rep(j, s[i].size()) { rep(k, 3) { rwa[k][i][j + 1] += rwa[k][i][j]; } } } if (!ej || !eo || !ei) { cout << -1 << endl; return 0; } memo(); int ans = 1e15; rep(i, n) {//文字列1個 rep(j, s[i].size()) { for (int k = j; k < s[i].size(); k++) { if (rwa[1][i][k + 1] - rwa[1][i][j] < K)continue; int jr = max(0ll, K - rwa[0][i][j]); int ji = max(0ll, K - rwa[2][i][s[i].size()] + rwa[2][i][k+1]); ans = min(ans, c[i] + dp[0][n][jr] + dp[2][n][ji]); } } } rep(i, n) { rep(j, n) {//文字列2個 rep(k, s[i].size() + 1) { rep(l, s[j].size() + 1) { int jr = max(0ll, K - rwa[0][i][k]); int jo = max(0ll, K - rwa[1][i][s[i].size()]+rwa[1][i][k] - rwa[1][j][l]); int ji = max(0ll, K - rwa[2][j][s[j].size()]+rwa[2][j][l]); ans = min(ans, c[i] + c[j] + dp[0][n][jr] + dp[1][n][jo] + dp[2][n][ji]); } } } } cout << ans << endl; }