結果
| 問題 | No.1029 JJOOII 3 |
| ユーザー |
 Mister
|
| 提出日時 | 2020-04-23 13:25:58 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,173 bytes |
| コンパイル時間 | 700 ms |
| コンパイル使用メモリ | 86,628 KB |
| 実行使用メモリ | 13,888 KB |
| 最終ジャッジ日時 | 2024-04-21 13:23:36 |
| 合計ジャッジ時間 | 6,945 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
12,192 KB |
| testcase_01 | AC | 2 ms
6,944 KB |
| testcase_02 | AC | 2 ms
6,944 KB |
| testcase_03 | AC | 642 ms
6,944 KB |
| testcase_04 | TLE | - |
| testcase_05 | TLE | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
ソースコード
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
template <class T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }
using lint = long long;
constexpr lint INF = 1LL << 60;
const std::string JOI = "JOI$";
void solve() {
int n, k;
std::cin >> n >> k;
std::vector<std::pair<std::string, lint>> ps(n);
for (auto& p : ps) {
std::cin >> p.first >> p.second;
}
auto cnt = vec(3, vec(n, 0LL));
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < n; ++j) {
cnt[i][j] = std::count(ps[j].first.begin(), ps[j].first.end(), JOI[i]);
}
}
std::vector<lint> dp(k * 3 + 1, INF);
dp[0] = 0;
for (int l = 0; l < k * 3; ++l) {
for (const auto& p : ps) {
int r = l;
for (char c : p.first) {
if (c == JOI[r / k]) ++r;
}
if (r > l) dp[r] = std::min(dp[r], dp[l] + p.second);
}
}
auto ans = dp.back();
std::cout << (ans == INF ? -1 : ans) << std::endl;
}
int main() {
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
solve();
return 0;
}