結果
問題 | No.1029 JJOOII 3 |
ユーザー |
![]() |
提出日時 | 2020-04-17 22:32:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 59 ms / 2,000 ms |
コード長 | 3,380 bytes |
コンパイル時間 | 1,078 ms |
コンパイル使用メモリ | 114,864 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-03 14:08:41 |
合計ジャッジ時間 | 3,182 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
// #define _GLIBCXX_DEBUG // for STL debug (optional) #include <iostream> #include <iomanip> #include <cstdio> #include <string> #include <cstring> #include <deque> #include <list> #include <queue> #include <stack> #include <vector> #include <utility> #include <algorithm> #include <map> #include <set> #include <complex> #include <cmath> #include <limits> #include <cfloat> #include <climits> #include <ctime> #include <cassert> #include <numeric> #include <fstream> #include <functional> #include <bitset> using namespace std; using ll = long long int; using int64 = long long int; template<typename T> void chmax(T &a, T b) {a = max(a, b);} template<typename T> void chmin(T &a, T b) {a = min(a, b);} template<typename T> void chadd(T &a, T b) {a = a + b;} int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; const int INF = 1LL << 29; const ll LONGINF = 1LL << 60; const ll MOD = 1000000007LL; ll dp1[100010][3], dp2[250]; int inc[85][3], nxt[85][3], pre[85][85][3], suf[85][85][3]; int main() { int N, K; scanf("%d%d", &N, &K); vector<string> S(N); vector<ll> C(N); for(int i=0; i<N; i++) cin >> S[i], scanf("%lld", &C[i]); const string pat = "JOI"; vector< vector< vector<int> > > pos(N, vector< vector<int> >(3)); for(int i=0; i<N; i++) { int L = S[i].size(); for(int j=0; j<L; j++) { pos[i][ pat.find(S[i][j]) ].emplace_back(j); } } ll ans = LONGINF; if(K <= 80) { fill(dp2, dp2 + 3*K + 1, LONGINF); dp2[0] = 0; for(int p=0; p<3*K; p++) { for(int i=0; i<N; i++) { int L = S[i].size(), ptr = p; for(int j=0; j<L and ptr < 3*K; j++) { int t = ptr / K; ptr += (S[i][j] == pat[t]); } chmin(dp2[ptr], dp2[p] + C[i]); } } ans = dp2[3*K]; } else { fill(dp1[0], dp1[K+1], LONGINF); dp1[0][0] = 0; for(int x=0; x<3; x++) { for(int p=0; p<K; p++) { if(dp1[p][x] == LONGINF) continue; for(int i=0; i<N; i++) { int rem = K - p, ava = pos[i][x].size(); if(rem > ava) { int np = p + ava; chmin(dp1[np][x], dp1[p][x] + C[i]); } else { ava = min(ava, rem); int cur = pos[i][x][ava - 1]; if(x == 2) { chmin(dp1[K][x], dp1[p][x] + C[i]); } else { int nx = x + 1; int c = upper_bound(pos[i][nx].begin(), pos[i][nx].end(), cur) - pos[i][nx].begin(); int cnt = (int)pos[i][nx].size() - c; // fprintf(stderr, "i = %d: p = %d, x = %d, cnt = %d\n",i, p, x, cnt); chmin(dp1[cnt][nx], dp1[p][x] + C[i]); } } } } } ans = dp1[K][2]; } if(ans == LONGINF) cout << -1 << endl; else cout << ans << endl; return 0; }