結果

問題 No.1029 JJOOII 3
コンテスト
ユーザー i_mrhj
提出日時 2020-05-16 04:31:20
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,640 bytes
コンパイル時間 1,009 ms
コンパイル使用メモリ 105,560 KB
実行使用メモリ 11,284 KB
最終ジャッジ日時 2024-09-21 07:51:41
合計ジャッジ時間 3,209 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <climits>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>
#include <cstdio>
#include <climits>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#include <set>
#include <map>
#include <complex>

#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
long long MOD = 1000000007;
long long INF = 1000000000000000000; //10^18
typedef long long ll;
typedef unsigned long long ull;


ll powMod(ll x, ll n, ll mod) {
  if (n == 0) return 1;
  ll t = powMod(x, n/2, mod);
  t = t * t % mod;
  if (n & 1) return t * x % mod;
  return t;
}

ll gcd(ll a, ll b) {
  if (a == 0 || b == 0) return a + b;
  if (b > a) return gcd(b, a);
  return gcd(b, a % b);
}

ll c[100300], mj[100300], mo[100300], mi[100300];
int mjm[100300], mom[100300], mim[100300];

int main(void) {

  int n, k;
  string s[100300];
  
  scanf("%d %d", &n, &k);
  rep(i, n) {
    cin >> s[i];
    scanf("%lld", &c[i]);
  }

  vector< pair<int, int> > J, O, I;
  rep(w, n) {
    int j = 0, o = 0, i = 0;
    rep(l, s[w].size()) {
      if (s[w][l] == 'J') j++;
      if (s[w][l] == 'O') o++;
      if (s[w][l] == 'I') i++;
    }
    if (j > 0) J.push_back(make_pair(w, j));
    if (o > 0) O.push_back(make_pair(w, o));
    if (i > 0) I.push_back(make_pair(w, i));
  }

  //cout << endl;
  //rep(i, I.size()) cout << s[I[i].first] << " " << I[i].second << endl;

  if (J.size() * O.size() * I.size() == 0) {
    printf("-1\n");
    return 0;
  }

  for (int i = 1; i <= k + 100; i++) mj[i] = INF, mo[i] = INF, mi[i] = INF;

  for (int i = 1; i <= k + 100; i++) {
    //cout << -1 << endl;
    rep(j, J.size()) {
      if (J[j].second > i) ;
      else mj[i] = min(mj[i], mj[i-J[j].second]+c[J[j].first]);
    }
    rep(j, O.size()) {
      if (O[j].second > i) ;
      else mo[i] = min(mo[i], mo[i-O[j].second]+c[O[j].first]);
    }
    rep(j, I.size()) {
      if (I[j].second > i) ;
      else mi[i] = min(mi[i], mi[i-I[j].second]+c[I[j].first]);
    }
  }

  mjm[k + 100] = k + 100;
  mom[k + 100] = k + 100;
  mim[k + 100] = k + 100;
  for (int i = k + 99; i >= 0; i--) {
    if (mj[i] < mj[mjm[i+1]]) mjm[i] = i;
    else mjm[i] = mjm[i+1];
    if (mi[i] < mi[mim[i+1]]) mim[i] = i;
    else mim[i] = mim[i+1];
    if (mo[i] < mo[mom[i+1]]) mom[i] = i;
    else mom[i] = mom[i+1];
  }
    

  
  //rep(i, k) cout << mj[i] << endl;
  //cout << endl;
  //cout << "I" << endl;
  //rep(i, k + 5) cout << mi[i] << endl;
  //cout << endl;

  ll f[3][100] = {};
  int r1 = 0;
  rep(i, J.size()) {
    int jc = 0, oc = 0, ic = 0;
    if (J[i].second >= k) {
      rep(j, s[J[i].first].size()) {
	if (s[J[i].first][j] == 'J') jc++;
	if (jc >= k && s[J[i].first][j] == 'O') oc++;
	if (oc >= k && s[J[i].first][j] == 'I') ic++;
      }
      f[0][r1] = c[J[i].first];
      f[1][r1] = oc;
      f[2][r1] = ic;
      r1++;
    } else {
      int e = k - J[i].second;
      e = mjm[e];
      if (e >= k) continue;
      rep(j, s[J[i].first].size()) {
	if (s[J[i].first][j] == 'J') jc++;
	if (jc >= k - e && s[J[i].first][j] == 'O') oc++;
	if (oc >= k && s[J[i].first][j] == 'I') ic++;
      }
      f[0][r1] = mj[e] + c[J[i].first];
      f[1][r1] = oc;
      f[2][r1] = ic;
      r1++;
    }
  }

  ll b[2][100];
  int r2 = 0;
  rep(i, I.size()) {
    int ic = 0, oc = 0;
    if (I[i].second >= k) {
      rep(j, s[I[i].first].size()) {
	if (s[I[i].first][s[I[i].first].size()-1-j] == 'I') ic++;
	if (ic >= k && s[I[i].first][s[I[i].first].size()-1-j] == 'O') oc++;
      }
      b[0][r2] = c[I[i].first];
      b[1][r2] = oc;
      r2++;
    } else {
      int e = k - I[i].second;
      e = mim[e];
      if (e >= k) continue;
      rep(j, s[I[i].first].size()) {
	if (s[I[i].first][s[I[i].first].size()-1-j] == 'I') ic++;
	if (ic >= k - e && s[I[i].first][s[I[i].first].size()-1-j] == 'O') oc++;
      }
      b[0][r2] = mi[e] + c[I[i].first];
      b[1][r2] = oc;
      r2++;
    }
  }

  //rep(i, r1) cout << f[0][i] << " " << f[1][i] << " " << f[2][i] << endl;
  //rep(i, r2) cout << b[0][i] << " " << b[1][i] << endl;

  ll ans = LLONG_MAX;
  rep(i, r1) {
    if (f[2][i] >= k) ans = min(ans, f[0][i]);
    else if (0 < f[2][i] && f[2][i] < k) {
      int e = k - f[2][i];
      e = mim[e];
      ans = min(ans, f[0][i] + mi[e]);
    } else {
      //if (i == 2) cout << 99999 << endl;
      rep(j, r2) {
	int z = k - f[1][i] - b[1][j];
	
	if (z <= 0) ans = min(ans, f[0][i] + b[0][j]);
	else {
	  z = mom[z];
	  ans = min(ans, f[0][i] + b[0][j] + mo[z]);
	}
      }
    }
  }

  cout << ans << endl;

  return 0;

}
0