#465942 (C++14) No.1029 JJOOII 3

• 問題: No.1029 JJOOII 3
• ユーザー: Enjapma_kyopro
• 提出日時: 2020-04-17 22:22:40
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 68 ms / 2,000 ms
• コード長: 6,000 bytes
• コンパイル時間: 1,629 ms
• コンパイル使用メモリ: 180,216 KB
• 実行使用メモリ: 6,820 KB
• 最終ジャッジ日時: 2024-10-03 13:51:54
• 合計ジャッジ時間: 4,656 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	4 ms; 6,820 KB
testcase_01	AC	4 ms; 6,820 KB
testcase_02	AC	5 ms; 6,820 KB
testcase_03	AC	13 ms; 6,820 KB
testcase_04	AC	13 ms; 6,816 KB
testcase_05	AC	57 ms; 6,816 KB
testcase_06	AC	54 ms; 6,820 KB
testcase_07	AC	51 ms; 6,820 KB
testcase_08	AC	51 ms; 6,816 KB
testcase_09	AC	52 ms; 6,816 KB
testcase_10	AC	51 ms; 6,816 KB
testcase_11	AC	53 ms; 6,816 KB
testcase_12	AC	49 ms; 6,816 KB
testcase_13	AC	50 ms; 6,816 KB
testcase_14	AC	53 ms; 6,816 KB
testcase_15	AC	56 ms; 6,816 KB
testcase_16	AC	53 ms; 6,816 KB
testcase_17	AC	58 ms; 6,820 KB
testcase_18	AC	48 ms; 6,816 KB
testcase_19	AC	5 ms; 6,820 KB
testcase_20	AC	34 ms; 6,820 KB
testcase_21	AC	35 ms; 6,816 KB
testcase_22	AC	35 ms; 6,816 KB
testcase_23	AC	37 ms; 6,816 KB
testcase_24	AC	33 ms; 6,820 KB
testcase_25	AC	34 ms; 6,820 KB
testcase_26	AC	50 ms; 6,816 KB
testcase_27	AC	52 ms; 6,820 KB
testcase_28	AC	50 ms; 6,820 KB
testcase_29	AC	48 ms; 6,820 KB
testcase_30	AC	54 ms; 6,820 KB
testcase_31	AC	52 ms; 6,816 KB
testcase_32	AC	68 ms; 6,820 KB
testcase_33	AC	68 ms; 6,820 KB
testcase_34	AC	62 ms; 6,820 KB
testcase_35	AC	63 ms; 6,820 KB
testcase_36	AC	65 ms; 6,816 KB
testcase_37	AC	3 ms; 6,820 KB
testcase_38	AC	4 ms; 6,820 KB
testcase_39	AC	4 ms; 6,820 KB
testcase_40	AC	5 ms; 6,820 KB

ソースコード

#include <bits/stdc++.h>
#include <unistd.h>
#include <sys/time.h>
#include <stdlib.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P, ll> T;
 
long long int INF = 2e18;
const ll fact_table = 1200008;
double Pi = 3.1415926535897932384626;

priority_queue <ll> pql;
priority_queue <P> pqp;
priority_queue <P> bag;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop
 
ll dx[8]={1,0,-1,0,1,1,-1,-1};
ll dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//↓,→,↑,←

#define endl "\n"
#ifdef ENJAPMA
    #undef endl
#endif
#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define CLEAR(a) a = decltype(a)(); 
#define pc(x) cout << x << ",";
 
// const ll mod = 998244353ll;
const ll mod = 1000000007ll;
  
ll mypow(ll number1,ll number2, ll mod){
    if(number2 == 0){
        return 1ll;
    }else{
        ll number3 = mypow(number1,number2 / 2, mod);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
void YES(bool condition){
    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){
    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}
 
/*
ll fact[fact_table + 5],rfact[fact_table + 5]; 
 
void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=fact_table; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[fact_table] = mypow(fact[fact_table],mod - 2, mod);
    for(ll i=fact_table; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod ) * rfact[n-r]) % mod;}
*/

bool multicase = false;

ll n,m,num,a,b,c,d,e,h,q;
ll w, k, l, r;
string s[85];
ll cost[85];
ll cj[85], co[85], ci[85];

vector<P> Jv, Ov, Iv;
vector<T> JO, OI, JOI;

ll tablej[100005], tableo[100005], tablei[100005];


void solve(){
    ll K;
    cin >> n >> K;
    for(ll i=0;i<n;i++){
        cin >> s[i] >> cost[i];
    }
    for(ll i=0;i<n;i++){
        ll J = 0, O = 0, I = 0;
        for(ll j=0;j<s[i].size();j++){
            if(s[i][j] == 'J')J++;
            if(s[i][j] == 'O')O++;
            if(s[i][j] == 'I')I++;
        }
        ll a, b;
        a = 0, b = O;

        JO.pb(T(P(a, b), cost[i]));
        // JOのカウント
        for(ll j=0;j<s[i].size();j++){
            if(s[i][j] == 'J'){
                a++;
                JO.pb(T(P(a, b), cost[i]));
            }
            if(s[i][j] == 'O')b--;
        }

        a = 0, b = I;

        OI.pb(T(P(a, b), cost[i]));
        for(ll j=0;j<s[i].size();j++){
            if(s[i][j] == 'O'){
                a ++;
                OI.pb(T(P(a, b), cost[i]));
            }
            if(s[i][j] == 'I')b--;
        }

        // JOIのカウントをしないといけない
        for(ll j=0;j<=s[i].size();j++){
            cj[j] = co[j] = ci[j] = 0;
        }
        J = 0, O = 0, I = 0;
        for(ll j=0;j<s[i].size();j++){
            if(s[i][j] == 'J')J++;
            if(s[i][j] == 'O')O++;
            if(s[i][j] == 'I')I++;
            cj[j] = J, co[j] = O, ci[j] = I;
        }
        for(ll j=0;j<s[i].size();j++){
            for(ll k=j;k<s[i].size();k++){
                ll myJ, myO, myI;
                myJ = cj[j-1];
                myO = co[k] - co[j-1];
                myI = ci[s[i].size()-1] - ci[k];
                if(myO >= K){
                    JOI.pb(T(P(myJ, myI), cost[i]));
                }
            }
        }
        Jv.pb(P(J, cost[i]));
        Ov.pb(P(O, cost[i]));
        Iv.pb(P(I, cost[i]));
    }
    ll k = K;
    for(ll i=1;i<=100000;i++){
        tablej[i] = tableo[i] = tablei[i] = INF;
    }
    for(ll i=1;i<=100000;i++){
        for(ll j=0;j<Jv.size();j++){
            if(i >= Jv[j].first)tablej[i] = min(tablej[i], tablej[i - Jv[j].first] + Jv[j].second);
        }
        for(ll j=0;j<Ov.size();j++){
            if(i >= Ov[j].first)tableo[i] = min(tableo[i], tableo[i - Ov[j].first] + Ov[j].second);
        }
        for(ll j=0;j<Iv.size();j++){
            if(i >= Iv[j].first)tablei[i] = min(tablei[i], tablei[i - Iv[j].first] + Jv[j].second);
        }
    }
    for(ll i=99999;i>=1;i--){
        tablej[i] = min(tablej[i], tablej[i+1]);
        tableo[i] = min(tableo[i], tableo[i+1]);
        tablei[i] = min(tablei[i], tablei[i+1]);
    }
    ll ans = tablej[k] + tableo[k] + tablei[k];
    for(ll i=0;i<JO.size();i++){
        for(ll j=0;j<OI.size();j++){
            ll nj, no, ni;
            nj = k - JO[i].first.first;
            no = k - JO[i].first.second - OI[j].first.first;
            ni = k - OI[j].first.second;
            ll tmp = JO[i].second + OI[j].second;
            if(nj > 0)tmp += tablej[nj];
            if(no > 0)tmp += tableo[no];
            if(ni > 0)tmp += tablei[ni];
            ans = min(ans, tmp);

        }
    }
    for(ll i=0;i<JOI.size();i++){
        ll nj, no, ni;
        nj = k - JOI[i].first.first;
        ni = k - JOI[i].first.second;
        ll tmp = JOI[i].second;
        if(nj > 0)tmp += tablej[nj];
        if(ni > 0)tmp += tablei[ni];

        ans = min(ans, tmp);
    }
    if(ans > INF / 2){
        p(-1);
    }else{
        p(ans);
    }



    return;
}


int main(){
    // init();
    // インタラクティブになったらここは外しましょうね！！
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll q, testcase = 1;

    if(multicase){
        cin >> q;
    }else{ 
        q = 1;
    }
    while(q--){
        // pu("Case ");pu("#");pu(testcase);pu(": ");
        solve();
        testcase++;
    }
    
    // solve();
    return 0;

}