結果

問題 No.1029 JJOOII 3
ユーザー freecss00freecss00
提出日時 2020-04-19 01:14:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 217 ms / 2,000 ms
コード長 2,278 bytes
コンパイル時間 1,840 ms
コンパイル使用メモリ 175,764 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-04 00:39:19
合計ジャッジ時間 6,144 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 13 ms
6,820 KB
testcase_04 AC 43 ms
6,820 KB
testcase_05 AC 188 ms
6,816 KB
testcase_06 AC 131 ms
6,820 KB
testcase_07 AC 159 ms
6,816 KB
testcase_08 AC 180 ms
6,816 KB
testcase_09 AC 150 ms
6,816 KB
testcase_10 AC 156 ms
6,820 KB
testcase_11 AC 192 ms
6,816 KB
testcase_12 AC 107 ms
6,816 KB
testcase_13 AC 195 ms
6,820 KB
testcase_14 AC 203 ms
6,820 KB
testcase_15 AC 132 ms
6,816 KB
testcase_16 AC 155 ms
6,816 KB
testcase_17 AC 183 ms
6,820 KB
testcase_18 AC 188 ms
6,820 KB
testcase_19 AC 2 ms
6,816 KB
testcase_20 AC 2 ms
6,816 KB
testcase_21 AC 3 ms
6,820 KB
testcase_22 AC 3 ms
6,816 KB
testcase_23 AC 3 ms
6,820 KB
testcase_24 AC 2 ms
6,816 KB
testcase_25 AC 2 ms
6,816 KB
testcase_26 AC 3 ms
6,820 KB
testcase_27 AC 4 ms
6,816 KB
testcase_28 AC 3 ms
6,820 KB
testcase_29 AC 3 ms
6,816 KB
testcase_30 AC 4 ms
6,816 KB
testcase_31 AC 3 ms
6,820 KB
testcase_32 AC 213 ms
6,820 KB
testcase_33 AC 208 ms
6,816 KB
testcase_34 AC 217 ms
6,820 KB
testcase_35 AC 214 ms
6,820 KB
testcase_36 AC 210 ms
6,820 KB
testcase_37 AC 2 ms
6,816 KB
testcase_38 AC 1 ms
6,816 KB
testcase_39 AC 2 ms
6,816 KB
testcase_40 AC 2 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define REP(i,m,n) for(int i=(m); i<(int)(n); i++)
#define RREP(i,m,n) for(int i=(int)(n-1); i>=m; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define fi first
#define se second
#define debug(...) {cerr<<"[L"<<__LINE__<<"] "; _debug(__VA_ARGS__);}
template<typename T>
string join(const vector<T>&v, string del=", "){ stringstream s;
for(auto x : v) s << del << x; return s.str().substr(del.size());
}
template<typename T>
ostream& operator<<(ostream& o, const vector<T>&v){
if(v.size()) o << "[" << join(v) << "]"; return o;
}
template<typename T>
ostream& operator<<(ostream& o, const vector<vector<T> >&vv){
int l = vv.size();
if(l){ o<<endl; rep(i,l) o << (i==0 ? "[ " : ",\n " ) << vv[i] << (i==l-1 ? " ]" : ""); }
return o;
}
inline void _debug(){cerr<<endl;}
template<class First, class... Rest>
void _debug(const First& first, const Rest&... rest){cerr<<first<<" ";_debug(rest...);}
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
const double PI = (1*acos(0.0));
const double EPS = 1e-9;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const ll mod = 1e9 + 7;
inline void finput(string filename) {
freopen(filename.c_str(), "r", stdin);
}
int main(){
ios_base::sync_with_stdio(0);
// finput("./input");
ll N, K; cin >> N >> K;
vector<string> ss(N); vl cost(N);
rep(i,N) cin >> ss[i] >> cost[i];
string T = string(K, 'J') + string(K, 'O') + string(K, 'I') + string(100, '#');
string joi = "JOI";
vvl ccnt(N, vl(3));
rep(i,N) rep(c,3) ccnt[i][c] = count(all(ss[i]), joi[c]);
vl dp(3*K+1, INFL);
dp[0] = 0;
rep(i,3*K){
rep(j,N){
int pos = i;
if(T[i] == T[i+80]){
int c = joi.find(T[i]);
pos += ccnt[j][c];
}else{
for(auto c : ss[j]) if(T[pos] == c) pos++;
}
dp[pos] = min(dp[pos], dp[i] + cost[j]);
}
}
if(dp[3*K] == INFL){
cout << -1 << endl;
}else{
cout << dp[3*K] << endl;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0