結果
問題 | No.288 貯金箱の仕事 |
ユーザー | はまやんはまやん |
提出日時 | 2017-05-08 14:19:01 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 245 ms / 2,000 ms |
コード長 | 5,889 bytes |
コンパイル時間 | 1,691 ms |
コンパイル使用メモリ | 166,752 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 17:20:23 |
合計ジャッジ時間 | 6,662 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 6 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 245 ms
5,376 KB |
testcase_24 | AC | 119 ms
5,376 KB |
testcase_25 | AC | 4 ms
5,376 KB |
testcase_26 | AC | 4 ms
5,376 KB |
testcase_27 | AC | 4 ms
5,376 KB |
testcase_28 | AC | 3 ms
5,376 KB |
testcase_29 | AC | 3 ms
5,376 KB |
testcase_30 | AC | 65 ms
5,376 KB |
testcase_31 | AC | 66 ms
5,376 KB |
testcase_32 | AC | 126 ms
5,376 KB |
testcase_33 | AC | 126 ms
5,376 KB |
testcase_34 | AC | 185 ms
5,376 KB |
testcase_35 | AC | 186 ms
5,376 KB |
testcase_36 | AC | 245 ms
5,376 KB |
testcase_37 | AC | 67 ms
5,376 KB |
testcase_38 | AC | 169 ms
5,376 KB |
testcase_39 | AC | 79 ms
5,376 KB |
testcase_40 | AC | 86 ms
5,376 KB |
testcase_41 | AC | 236 ms
5,376 KB |
testcase_42 | AC | 205 ms
5,376 KB |
testcase_43 | AC | 144 ms
5,376 KB |
testcase_44 | AC | 43 ms
5,376 KB |
testcase_45 | AC | 133 ms
5,376 KB |
testcase_46 | AC | 206 ms
5,376 KB |
testcase_47 | AC | 99 ms
5,376 KB |
testcase_48 | AC | 145 ms
5,376 KB |
testcase_49 | AC | 61 ms
5,376 KB |
testcase_50 | AC | 86 ms
5,376 KB |
testcase_51 | AC | 60 ms
5,376 KB |
testcase_52 | AC | 114 ms
5,376 KB |
testcase_53 | AC | 148 ms
5,376 KB |
testcase_54 | AC | 83 ms
5,376 KB |
testcase_55 | AC | 2 ms
5,376 KB |
ソースコード
/* ` `` ` . ` .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; }