結果

問題 No.288 貯金箱の仕事
ユーザー 👑 はまやんはまやんはまやんはまやん
提出日時 2017-05-08 14:19:01
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 250 ms / 2,000 ms
コード長 5,889 bytes
コンパイル時間 1,549 ms
コンパイル使用メモリ 164,520 KB
実行使用メモリ 4,572 KB
最終ジャッジ日時 2023-10-12 18:55:10
合計ジャッジ時間 7,173 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
4,424 KB
testcase_01 AC 2 ms
4,352 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 1 ms
4,348 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 6 ms
4,424 KB
testcase_06 AC 1 ms
4,352 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 2 ms
4,352 KB
testcase_13 AC 1 ms
4,348 KB
testcase_14 AC 2 ms
4,352 KB
testcase_15 AC 2 ms
4,348 KB
testcase_16 AC 2 ms
4,352 KB
testcase_17 AC 2 ms
4,352 KB
testcase_18 AC 2 ms
4,348 KB
testcase_19 AC 2 ms
4,352 KB
testcase_20 AC 2 ms
4,352 KB
testcase_21 AC 2 ms
4,348 KB
testcase_22 AC 2 ms
4,348 KB
testcase_23 AC 250 ms
4,352 KB
testcase_24 AC 122 ms
4,352 KB
testcase_25 AC 3 ms
4,572 KB
testcase_26 AC 3 ms
4,364 KB
testcase_27 AC 3 ms
4,368 KB
testcase_28 AC 3 ms
4,352 KB
testcase_29 AC 3 ms
4,452 KB
testcase_30 AC 66 ms
4,376 KB
testcase_31 AC 66 ms
4,352 KB
testcase_32 AC 127 ms
4,352 KB
testcase_33 AC 128 ms
4,476 KB
testcase_34 AC 189 ms
4,560 KB
testcase_35 AC 189 ms
4,360 KB
testcase_36 AC 250 ms
4,424 KB
testcase_37 AC 68 ms
4,352 KB
testcase_38 AC 170 ms
4,352 KB
testcase_39 AC 80 ms
4,352 KB
testcase_40 AC 86 ms
4,408 KB
testcase_41 AC 240 ms
4,500 KB
testcase_42 AC 209 ms
4,440 KB
testcase_43 AC 146 ms
4,440 KB
testcase_44 AC 44 ms
4,348 KB
testcase_45 AC 135 ms
4,348 KB
testcase_46 AC 211 ms
4,500 KB
testcase_47 AC 100 ms
4,348 KB
testcase_48 AC 145 ms
4,352 KB
testcase_49 AC 61 ms
4,352 KB
testcase_50 AC 87 ms
4,352 KB
testcase_51 AC 62 ms
4,352 KB
testcase_52 AC 115 ms
4,364 KB
testcase_53 AC 149 ms
4,364 KB
testcase_54 AC 85 ms
4,352 KB
testcase_55 AC 1 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*                                                                                 `
                                                                                ``  `
                                                                          . `   .g,`
                   Welcome To My Coding Space!                          .MMe  `(F(#~ `.J,
                                                                       `.M/7b. dD.N; (#=#:
                                                                     ``  db (m.#` Wl(@ jF    `
                                            ``    `  `          `   ..+kMMN;_(Y> `(TD  d$..gHN_
                                     `   ``   ......   `  `  ` `..gMB61+1+dK `- `.    .TM@^(d%
                               `` `` ..JggHHMMHHYYTHMMMNmgJ.. .kB6z?1+z1+<dD ..` .  ``.` `.V'
                              ``..+HMBYC1?1+???=?====????1vTHMNe+1+dMB"BMMM% .`je. `.. ..+@`
                            `..gM9C1+?==??==?==?=?===??=??=?1?zTMNeJTHg..``...`.,S._`.` d$  `
                      ` ` .(kBY1+==????=?=??=?=??=???=?=?=?=????+zTMm+?TMm..   ` d[ .``.M}
                       `.(M9++?=????==???=?=??=?=?=?=?=?=?=?===?==1+7Mmx?MN,``..._^`.. (F      `
     ` ` ` ` `  `      (M8++z11==?==??==??=?==?=?=?==??=??=??==??==?=+7Mm<dNg, ` .`.. (#!   `
   ` `    ..(JgH@MMMMMMB1+=??=??=?????==11??1=1?1?=1+=11?1==?=1=??=??11+WNJdMt .``.` J#! `
      .(HHYYC?1+??z>+H8+=??=?=?=???=?=?=z1&z1?==?1<dNs111?==1ux?==?=?==1zdNcW%  ..`. J#~`
     `.WNx<?1?==1=zdMD+=?==?===?=?==?===<dNNx1z??==+WMN+g&&&xdMk1??=1===???MN}`.`.`. J#` `
  `     ?MNc1=1?z?jH8+==?=?==??=jQ21=?=?(M$?WNx<1=zudMMMszOCvTHMmx+?1?z+1?zd#:..`.`. J@       `
     `` .M81==?==>dM<??===?=?=?+dNy+?=?jM@ ` ?WNe+zO>dNcHmJ1+1JMMR1?z??Ne1<d#~.`..`. dF
       (M3+1+?==?jMD+=?z1&&?v1+jMMb+=?1d#!`..``?HNx+?+HR ?Mm+1<dMMp?==<dNc<d#_.`..`.`dF  `
      ,MHmax111=<dNC?=?=(M#ugH9M#W#6+?(M'`.`.... ?WNe<dM: .TNm<dN?Nm<=zzMR+M@` .``.. dF `
   ` ``  _CM$+??1d#<==?=>dM9+?(MF(MI+jMf .`.``.`.. (TNaHr`.`.TNmN:(MR+?zMK(M$` `.`.``dF        `
          J#<=1<jME+1?=1d9Mn1<jN! qN(d@_.`..`.`.`.```-7Y5.....,TB! (MmJ+MH(M: ...`.`.d$`
     `   .M$iggWWMR+1?<dDjMNxjMB  .NgN``..``.`.``....`.d#Y"""YWNg.  .WNxW#J@ .`.`.``.H: `
         _Y""!  .M$jm+?1zd#TNzM}.. ?M% .`..`.`..``.`..  .+NMNg,.?Mm._ ?NMNM$ ..`..``.#    `
                .HPj#z=?<d#_WM#:.JgHH6 .  `.`.`..``.`.`jMMF`.MMN..TN,  ?@jM}`..`.`.`JD   `
           ` `   dbjMI?=+MF`.7XME^_.--,. ..`.``.`..`.`.M#XNgjNdMR. ?N-.  (#~``.``.. d%
              `  d#<WR1z(Mt` (#' (MMBTHNe.`..`..`.`.` .M#UMMMM#W#_. zN.  dF`.`...`..H}  `
                 ?MO(N+?jM:`.M!`.M9N+.-MMR `..`..`.`.`_?MmTMMMwM#~...H: .H}`..`..` (#`
          `  `  ` WNJMR<dN_ JB  dNwMMMMNdM[`.`.`.`.`..  ,TNNggMB! .` ~ `(M `.`.``. dF
                 `.MdMNoW@ `JP `(MKdMMNMdM}`.`..`.`.`.... .??!`.`.`..`..dD .`....`.W'
                   ?MMMMMP `(R`..?MmyUWQMB ..`..`.`.`..`..`..`.`.`_`-.gM#!.`.``.``.@
             `   `` _7NTMN.`.H/`. ,TMMB"! .``.`.`..`.``.``.`..`.`. .,NIdb` .`..`  j$
          `           Wm.M;`._!..`.`...`_`...``..   ...(+ga,`.....``(NjMr`..`... .#:
                      .MpdN_.`. ``.``.`..`..(-JggkWY9YC<>;?Wp .``.` J#>dN, ..``.`dF`
                      `_UmMn .`..`..`..`. JMYT1<;;;>>>>>;>>?Wo ..`. dK1=dN,`..``.MN+
                        .dMMe .`.``.`.`.` d#<;>>>>;>>>>;>>>>(N,`.. -MK1llvWm.   JM?Mp. ` `
                     ` .M9+?Me`.`..`.`.`` JN(>;>>;>>;>>>;>>><db` (kH5lllllzXMm.-NNszWm ` `
                `     (#1+???Hm, ..`..`..`(N:>>>>>;>>>>>;>>><d@_.JNZIlllllllzvTWB6zlJMp      `
                ` `` j@1+==?1zvHm.`...`....Hc<>>>>>>>>>>>>><(W$(M8TIllllllllllllllllzvMo ` `   `
                    (#1?==1?===z?TNa,.` `` (Ne<<>>>>><;><;jgMMY1HK1lllllllllllllllllllJMp `
                   .Ne&g&x1=?=?==?1zTHNmJ-...dNgJ++++&ggMH9=~ .M9Izlllllllllllllllllll1WF    `
                `   _???MK<=??=??1z?(MM@!d#M#Y""""=<!!~```  .d8Illllllll=lll=lllllllzudY `     `
                `       dH<?+uev?=1uMM^  d@vN&.`...`.`.`.-JH91zzl=llllllllllll=lzllzd#'  `  `
                        ,MNMBHNIvjdB(D ` d#=zTNm.....JgHM9Izlllludk=zl=ll=llllllvug#^
                     ` `    `.MmgM=+M$ ` d#zzO1vUUUU9TI=lllzzO1dKT#zOlllll=llll=dM=
                         `   `(Y^ JBdr ` dNmxzIlllllllllllz1ug#= .My1llllllllllzdD `
                           `     j@1dR ``(#~THaxl=lzzlzzzugW"!` ``,Nzlzz=lllllzd#:  `
                            ` ` .#z=d# ``(#_` .7THWQkWHB"^ ` `   ` ?NsIzzlll=ljM\
                       `   ``  (M6zldN_` .M| `    ``    `           .WezllzllzH% `` `
                     `    `  .+#Czl=dM;`  dR                    `     4m+zll1dD
                        `  `.d@1llzvdMb   ,#   `                   `   ?Wmxzdf                     */
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------



typedef long long ll;
int N, A[505];
ll M, K[505];
//---------------------------------------------------------------------------------------------------
#define INF INT_MAX/2
int dp[1010101]; int ma;
void makedp() {
    ma = A[N - 1];
    rep(i, 0, ma*ma) dp[i] = INF;
    dp[0] = 0;
    rep(i, 1, ma*ma) rep(j, 0, N) {
        int ii = i - A[j];
        if (0 <= ii) dp[i] = min(dp[i], dp[ii] + 1);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> K[i];

    makedp();

    ll sm = 0;
    rep(i, 0, N) sm += A[i] * K[i];

    ll d = sm - M;
    if (d < 0) {
        printf("-1\n");
        return;
    }

    ll rest = d % (ma * ma);
    ll ans = (d - rest) / ma;
    if (dp[rest] == INF) {
        printf("-1\n");
        return;
    }
    ans += dp[rest];
    cout << ans << endl;
}
0