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

提出ソース

結果

問題	No.1029 JJOOII 3
ユーザー	i_mrhj
提出日時	2020-05-16 03:47:19
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	4,616 bytes
コンパイル時間	997 ms
コンパイル使用メモリ	104,000 KB
実行使用メモリ	11,024 KB
最終ジャッジ日時	2024-09-19 19:58:04
合計ジャッジ時間	2,860 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 6,784 KB
testcase_01	AC	3 ms 6,784 KB
testcase_02	AC	4 ms 6,784 KB
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	AC	45 ms 10,112 KB
testcase_14	WA	-
testcase_15	AC	4 ms 6,784 KB
testcase_16	AC	3 ms 6,912 KB
testcase_17	AC	4 ms 6,784 KB
testcase_18	WA	-
testcase_19	AC	4 ms 6,784 KB
testcase_20	WA	-
testcase_21	AC	4 ms 6,784 KB
testcase_22	AC	4 ms 6,784 KB
testcase_23	WA	-
testcase_24	WA	-
testcase_25	AC	4 ms 6,784 KB
testcase_26	WA	-
testcase_27	AC	4 ms 6,656 KB
testcase_28	WA	-
testcase_29	WA	-
testcase_30	AC	4 ms 6,784 KB
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	AC	4 ms 6,784 KB
testcase_38	AC	4 ms 6,784 KB
testcase_39	AC	4 ms 6,656 KB
testcase_40	AC	3 ms 6,656 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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 = 1000000000000000; //10^15
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[100100], mj[100100], mo[100100], mi[100100];
int mjm[100100], mom[100100], mim[100100];

int main(void) {

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

  vector< pair<int, int> > J, O, I;
  rep(k, n) {
    int j = 0, o = 0, i = 0;
    rep(l, s[k].size()) {
      if (s[k][l] == 'J') j++;
      if (s[k][l] == 'O') o++;
      if (s[k][l] == 'I') i++;
    }
    if (j > 0) J.push_back(make_pair(k, j));
    if (o > 0) O.push_back(make_pair(k, o));
    if (i > 0) I.push_back(make_pair(k, 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 + 80; i++) mj[i] = INF, mo[i] = INF, mi[i] = INF;

  for (int i = 1; i <= k + 80; i++) {
    //cout << -1 << endl;
    mj[i] = INF; mo[i] = INF; mi[i] = INF;
    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 + 80] = k + 80;
  mom[k + 80] = k + 80;
  mim[k + 80] = k + 80;
  for (int i = k + 79; 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] < mj[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];
      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];
      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;

}

yukicoder

結果

テストケース

ソースコード