結果
問題 | No.1029 JJOOII 3 |
ユーザー |
![]() |
提出日時 | 2020-04-17 22:37:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 66 ms / 2,000 ms |
コード長 | 1,140 bytes |
コンパイル時間 | 757 ms |
コンパイル使用メモリ | 77,192 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-03 14:16:29 |
合計ジャッジ時間 | 2,826 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <iostream> #include <cmath> #include <queue> #include <cassert> using namespace std; typedef long long ll; const ll INF=1e18; int main() { int n,k; cin>>n>>k; string t; for(int i=0;i<k;i++) t+="J"; for(int i=0;i<k;i++) t+="O"; for(int i=0;i<k;i++) t+="I"; string s[n]; ll c[n]; for(int i=0;i<n;i++) { cin>>s[i]>>c[i]; } int st[n][3]; fill(st[0], st[n], 0); for(int i=0;i<n;i++) { for(char ch:s[i]) { st[i][0] += ch == 'J'; st[i][1] += ch == 'O'; st[i][2] += ch == 'I'; } } ll v[3*k+1]; fill(v,v+3*k+1,INF); v[0]=0; for(int i=0;i<3*k;i++) { for(int j=0;j<n;j++) { int u; if (0 <= i && i<k-80) { u=i+st[j][0]; } else if (k<=i && i<2*k-80) { u=i+st[j][1]; } else if (2*k<=i && i<3*k-80) { u=i+st[j][2]; } else { u=i; for(char ch:s[j]) { if (ch == t[u]) u++; if (u == 3*k) break; } } v[u] = min(v[u], v[i]+c[j]); } } /* for(int i=0;i<=3*k;i++) { cout<<v[i]<<" "; } cout<<endl;*/ if (v[3*k] == INF) cout<<"-1"<<endl; else cout<<v[3*k]<<endl; }