結果
| 問題 | No.1029 JJOOII 3 |
| ユーザー |
 wk
|
| 提出日時 | 2020-04-29 15:32:46 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 228 ms / 2,000 ms |
| コード長 | 6,218 bytes |
| コンパイル時間 | 1,735 ms |
| コンパイル使用メモリ | 172,516 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-11-28 16:52:34 |
| 合計ジャッジ時間 | 5,526 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 38 |
ソースコード
#include <bits/stdc++.h>#define REP(i, n) for(int i = 0; (i) < (n); (i)++)#define INF 5000000000000000using namespace std;struct Edge{int to;long weight;Edge(int t, long w) : to(t), weight(w) {}};long modpow(long a, long n, long mod) {long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}// a^{-1} mod を計算するlong modinv(long a, long mod) {return modpow(a, mod - 2, mod);}struct compare1 {bool operator()(const pair<long, long>& value,const long& key){return (value.first < key);}bool operator()(const long& key,const pair<long, long>& value){return (key < value.first);}};struct UnionFind {vector<int> par;vector<int> rank;UnionFind(int n = 1){init(n);}void init(int n = 1){par.resize(n);rank.resize(n);REP(i, n) par[i] = i, rank[i] = 0;}int root(int x){if(par[x] == x) return x;else return par[x] = root(par[x]);}bool issame(int x, int y){return root(x) == root(y);}bool merge(int x, int y){x = root(x); y = root(y);if(x == y) return false;if(rank[x] < rank[y]) swap(x, y);if(rank[x] == rank[y]) rank[x]++;par[y] = x;return true;}};template<class Abel> struct weightedUnionFind{vector<int> par;vector<int> rank;vector<Abel> diff_weight;weightedUnionFind(int n = 1, Abel SUM_UNITY = 0){init(n, SUM_UNITY);}void init(int n = 1, Abel SUM_UNITY = 0){par.resize(n); rank.resize(n); diff_weight.resize(n);REP(i, n) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;}int root(int x){if(par[x] == x) return x;else{int r = root(par[x]);diff_weight[x] += diff_weight[par[x]];return par[x] = r;}}Abel weight(int x){root(x);return diff_weight[x];}bool issame(int x, int y){return root(x) == root(y);}bool merge(int x, int y, Abel w){w += weight(x); w -= weight(y);x = root(x); y = root(y);if(x == y) return false;if(rank[x] < rank[y]) swap(x, y), w = -w;if(rank[x] == rank[y]) rank[x]++;par[y] = x;diff_weight[y] = w;return true;}Abel diff(int x, int y){return weight(y) - weight(x);}};using Graph = vector<vector<int>>;using P = pair<long, long>;/*void dijkstra(int s, int V, Graph &G, long* d){priority_queue<P, vector<P>, greater<P>> pque;fill(d, d + V, INF);d[s] = 0;pque.push(P(0, s));while(!pque.empty()){P p = pque.top(); pque.pop();int now = p.second;if(d[now] < p.first) continue;REP(i, G[now].size()){Edge e = G[now][i];if(d[e.to] > d[now] + e.weight){d[e.to] = d[now] + e.weight;pque.push(P(d[e.to], e.to));}}}}*/long GCD(long a, long b){if(b == 0l) return a;if(a < b) return GCD(b, a);else return GCD(b, a%b);}int main(){int N, K; cin >> N >> K;string S[100]; long C[100];REP(i, N) cin >> S[i] >> C[i];long inf = 1000000000000000;int J[100], O[100], I[100];REP(i, N){int s = S[i].length();REP(j, s){if(S[i][j] == 'J') J[i]++;if(S[i][j] == 'O') O[i]++;if(S[i][j] == 'I') I[i]++;}}long dpJ[100005], dpO[100005], dpI[100005];dpJ[0] = 0l;dpO[0] = 0l;dpI[0] = 0l;REP(i, K){long temp = inf;REP(j, N){if(i+1 <= J[j]) temp = min(temp, C[j]);else if(J[j] >= 1) temp = min(temp, dpJ[i+1-J[j]] + C[j]);}dpJ[i+1] = temp;}REP(i, K){long temp = inf;REP(j, N){if(i+1 <= O[j]) temp = min(temp, C[j]);else if(O[j] >= 1) temp = min(temp, dpO[i+1-O[j]] + C[j]);}dpO[i+1] = temp;}REP(i, K){long temp = inf;REP(j, N){if(i+1 <= I[j]) temp = min(temp, C[j]);else if(I[j] >= 1) temp = min(temp, dpI[i+1-I[j]] + C[j]);}dpI[i+1] = temp;}//REP(i, K) cout << dpJ[i+1] << endl;if(dpJ[K] == inf || dpO[K] == inf || dpI[K] == inf) cout << -1 << endl;else{long ans = inf;REP(i, N) REP(j, N){int s1 = S[i].length();int s2 = S[j].length();int fj = 0;int fo = O[i];REP(k, s1+1){int so = 0;int si = I[j];REP(l, s2+1){long temp = 0l;if(fj < K) temp += dpJ[K-fj];temp += C[i];if(fo + so < K) temp += dpO[K-fo-so];temp += C[j];if(si < K) temp += dpI[K-si];ans = min(ans, temp);if(l != s2){if(S[j][l] == 'O') so++;if(S[j][l] == 'I') si--;}}if(k != s1){if(S[i][k] == 'J') fj++;if(S[i][k] == 'O') fo--;}}}REP(i, N){int s = S[i].length();for(int k=0;k<=s-3;k++) for(int l=k+1;l<=s-2;l++){int fj = 0, fo = 0, fi = 0;for(int j=0;j<=k;j++) if(S[i][j] == 'J') fj++;for(int j=k+1;j<=l;j++) if(S[i][j] == 'O') fo++;for(int j=l+1;j<=s-1;j++) if(S[i][j] == 'I') fi++;if(fo >= K){long temp = 0l;if(fj < K) temp += dpJ[K-fj];temp += C[i];if(fi < K) temp += dpI[K-fi];ans = min(ans, temp);}}}cout << ans << endl;}return 0;}