結果
| 問題 | No.1029 JJOOII 3 |
| ユーザー |
 wk
|
| 提出日時 | 2020-04-29 14:04:27 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,031 bytes |
| コンパイル時間 | 1,859 ms |
| コンパイル使用メモリ | 173,568 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-11-28 08:56:54 |
| 合計ジャッジ時間 | 4,599 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 10 WA * 28 |
ソースコード
#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();J[i] = 0;O[i] = 0;I[i] = 0;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 JO[100][100], OI[100][100];for(int i=1;i<=80;i++) for(int j=1;j<=80;j++){JO[i][j] = inf;OI[i][j] = inf;}REP(i, N){int s = S[i].length();int tempj = 0;int tempo = O[i];REP(j, s-1){if(S[i][j] == 'J') tempj++;if(S[i][j] == 'O') tempo--;if(tempj>0 && tempo > 0)JO[tempj][tempo] = min(JO[tempj][tempo], C[i]);}}REP(i, N){int s = S[i].length();int tempo = 0;int tempi = I[i];REP(j, s-1){if(S[i][j] == 'O') tempo++;if(S[i][j] == 'I') tempi--;if(tempo > 0 && tempi > 0)OI[tempo][tempi] = min(OI[tempo][tempi], C[i]);}}long JOI[100][100];for(int i=1;i<=80;i++) for(int j=1;j<=80;j++) JOI[i][j] = inf;REP(i, N){int s = S[i].length();int tempj = 0, tempo = 0, tempi = 0;for(int j=0;j<=s-3;j++) for(int k=j+1;k<=s-2;k++){for(int l=0; l<=j; l++) if(S[i][l] == 'J') tempj++;for(int l=j+1; l<=k; l++) if(S[i][l] == 'O') tempo++;for(int l=k+1;k<=s-1;k++) if(S[i][j] == 'I') tempi++;if(tempj>0 && tempo == K && tempi>0) JOI[tempj][tempi] = min(JOI[tempj][tempi], C[i]);}}//REP(i, N) cout << J[i] << endl;long dpJ[100005];dpJ[0] = 0l;REP(i, K){long temp = inf;REP(j, N) if(i+1 >= J[j] && J[j] >= 1) temp = min(temp, dpJ[i+1-J[j]] + C[j]);dpJ[i+1] = temp;}long dpO[100005];dpO[0] = dpJ[K];REP(i, K){long temp = inf;REP(j, 80) if(K-j-1>=0) temp = min(temp, dpJ[K-j-1] + JO[j+1][i+1]);REP(j, N) if(i+1 >= O[j] && O[j] >= 1) temp = min(temp, dpO[i+1-O[j]] + C[j]);dpO[i+1] = temp;}long dpI[100005];dpI[0] = dpO[K];REP(i, K){long temp = inf;REP(j, 80) if(K-j-1>=0) temp = min(temp, dpJ[K-j-1] + JOI[j+1][i+1]);REP(j, 80) if(K-j-1>=0) temp = min(temp, dpO[K-j-1] + OI[j+1][i+1]);REP(j, N) if(i+1 >= I[j] && I[j] >= 1) temp = min(temp, dpI[i+1-I[j]] + C[j]);dpI[i+1] = temp;}if(dpI[K] == inf) cout << -1 << endl;else cout << dpI[K] << endl;return 0;}