結果
問題 | No.1029 JJOOII 3 |
ユーザー | Rho |
提出日時 | 2020-04-16 20:37:55 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,952 bytes |
コンパイル時間 | 1,818 ms |
コンパイル使用メモリ | 167,420 KB |
実行使用メモリ | 198,396 KB |
最終ジャッジ日時 | 2024-04-10 07:07:07 |
合計ジャッジ時間 | 6,604 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 9 ms
17,152 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 11 ms
23,060 KB |
testcase_03 | AC | 29 ms
55,644 KB |
testcase_04 | AC | 27 ms
53,008 KB |
testcase_05 | AC | 119 ms
192,588 KB |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | AC | 111 ms
189,224 KB |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | AC | 110 ms
187,000 KB |
testcase_13 | AC | 112 ms
189,288 KB |
testcase_14 | WA | - |
testcase_15 | AC | 2 ms
6,944 KB |
testcase_16 | AC | 2 ms
6,940 KB |
testcase_17 | AC | 2 ms
6,944 KB |
testcase_18 | AC | 107 ms
184,316 KB |
testcase_19 | AC | 10 ms
23,228 KB |
testcase_20 | WA | - |
testcase_21 | AC | 74 ms
127,744 KB |
testcase_22 | AC | 78 ms
125,732 KB |
testcase_23 | AC | 75 ms
129,064 KB |
testcase_24 | AC | 75 ms
125,736 KB |
testcase_25 | AC | 80 ms
132,616 KB |
testcase_26 | AC | 107 ms
174,928 KB |
testcase_27 | AC | 119 ms
186,832 KB |
testcase_28 | AC | 113 ms
184,680 KB |
testcase_29 | AC | 108 ms
182,208 KB |
testcase_30 | WA | - |
testcase_31 | AC | 112 ms
182,248 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | AC | 177 ms
194,008 KB |
testcase_36 | WA | - |
testcase_37 | AC | 5 ms
12,340 KB |
testcase_38 | WA | - |
testcase_39 | AC | 9 ms
18,824 KB |
testcase_40 | AC | 9 ms
20,416 KB |
ソースコード
#include"bits/stdc++.h" using namespace std; #define int long long #define rep(i,n) for(int i=0;i<n;i++) const long long inf = 1e17; 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] = inf; 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 = inf; 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; }