結果

問題 No.1029 JJOOII 3
コンテスト
ユーザー betrue12
提出日時 2020-04-17 22:39:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 126 ms / 2,000 ms
コード長 905 bytes
コンパイル時間 2,691 ms
コンパイル使用メモリ 202,916 KB
最終ジャッジ日時 2025-01-09 20:25:26
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, K;
    cin >> N >> K;
    vector<string> S(N);
    vector<int> C(N);
    string JOI = "JOI";
    vector<vector<int>> cnt(N, vector<int>(3));
    for(int i=0; i<N; i++){
        cin >> S[i] >> C[i];
        for(int k=0; k<3; k++) cnt[i][k] = count(S[i].begin(), S[i].end(), JOI[k]);
    }
    string T = string(K, 'J') + string(K, 'O') + string(K, 'I') + string(100, '!');
    vector<int64_t> dp(3*K+1, 1e18);
    dp[0] = 0;
    for(int i=0; i<3*K; i++){
        for(int j=0; j<N; j++){
            int pos = i;
            if(T[i] == T[i+80]){
                pos += cnt[j][i/K];
            }else{
                for(char c : S[j]) if(T[pos] == c) pos++;
            }
            dp[pos] = min(dp[pos], dp[i] + C[j]);
        }
    }
    int64_t ans = dp[3*K];
    if(ans == 1e18) ans = -1;
    cout << ans << endl;
    return 0;
}
0