結果
問題 | No.496 ワープクリスタル (給料日前編) |
ユーザー |
![]() |
提出日時 | 2017-03-31 15:05:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 4,234 bytes |
コンパイル時間 | 695 ms |
コンパイル使用メモリ | 83,604 KB |
実行使用メモリ | 11,916 KB |
最終ジャッジ日時 | 2024-07-07 04:41:44 |
合計ジャッジ時間 | 1,375 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#include <iostream>#include <vector>#include <string>#include <algorithm>#include <cmath>#include <map>/*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::'''```````:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::''`_,-''.,... `:::::::::::::::::::::::::::::::::::::::::::::::::::::::' _,-',;;!!!!!!!!!; `::::::::::::::::::::::::::::::'`````:::::::::::::'' .-' ;<!!!!!!!'''`_..' `:::::::::::::::::::::::::'' ,;!!!;,`::::::::::' .-`.,,,zcccc,,cccd$$"",;> `:::::::::::::::::::::::' ;!!!!!!!!; ``:::::' ;' ,c$$$$$$$$$$$CC<<" ````_ :::::::::::::::::::::' ;!!!!!!!!!!!!!; ' ;! z$$$$$$$$$$$$$$$$$$$$$$??". ::::::::::::::::::::: <!!!!!!!!!!!!!' . .!',c$$$$$$$$$$$$$c, `"""',;;<!! :::::::::::::::::::: ,!!!!!!!!!!!'`,;! .<! ,$$$$$$$$$$$$$$$$hc,,,..- !!!! `:::::::::::::::::' <!!!!!!!!!' .<!!!;!! ,$$$$$""???$$$"""?????"" .<!!!! ::::::::::::::::: ;><!!!!!!!!! ,<!!!!!!!',c, "??.< . "??h. -;;;;!!!!!!!' ::::::::::::::::: !!!!!!!!!!' ;!!!!!!!!' d$$h.`$ccr,$h `;,." `!!!!!!!!! ::::::::::::::::::.`<!!!!!!!' !!!!!!!!!! dP"""?.`$$F`$$h.`!!!!!!!!!!!!!! .:::::::::::::::::::. <!!!!!! !!!!!!!!!! ,$ .nn.' "$$ P" <!!!!!!!!!!!' .:::::::::::::::::::::. <!!!! ;!!!!!!!!!! $$ MMMMx ?$ ,dx `!!!!!!!!!!' ::::::::::::::::::```:::: `!!! !!!'!!!!!! `$ MMMMMM, $r MMMr !!!!!!!!' .:::::::::::::::::::`!!;,.`' ``' ``,;!!!!' ch." 4MMMMMM "$ 4MMM `!!!!!' ..::::::::::::::::::::!!!!!'````'``<!!!'`.z$$$$. MMMMMMb $h MMM `!!'' .:::::::::::::::::::::::..``.,d$$$$$c,,,. $$$$$F"? "MMMMMM $$ 4P" ' .::::::::::::::::::::::::::dM""..""?$$$$$$$$$$$$$$$$$$c "MM" $$>` ,c `:::::::::::::::::::::::::MMn.`"?hc,d$$$$$$$$$$$$$$$$$$. `P $P' -??P== `:::::::::::::::::::::::MMMMMnx`"?$$$$$$$$$$$P".,.`"??$ccccc$.z$$$$. `' .:::::::::::::::::' ''MMMMMM,' .?$$$$$$$$$$ d$$$ d$$$$$$$$$$$$$h..``::::::::::::::::'MMMMMMMn `?$$$$$$$$$$,.?$$h. =."?$$$$$$$$$$$$$$hc,.``'::::::::::'MMMMMMMM ;, `"??$$$$$$h ?$$h. -m,``""??$$$$$$$$$$$$$c,.``````'MMMMMMM> !!! ?cc,.,d$$$$h.`"?$hc `P .`"?$$$$$$$$$$$$$$$$$$$ .:MMMMMMM ,!!'. $$$$$$$$$??=== `"""=c, " P n. "$$$$$$$$$$$$$$$$c_ ,.::::MMMMMMP !!! Mr<$$$$"".,c,;M ;<!! ..""=_ ' 4 .br .`""??$$$$$$$$??"".:::::::MMMMMM';!!',M>'$$$$$$$$$>4M `!!! 4MMbn.`"=cc," -'P",c=.,.`.. .= :::::::::MMMMM' !!! dMb $$$$$$$$P MM> !!! 4MMMMMMr :..`"-._""Pr4"'-P" .,.`:::::::::MMMM' <!!!,MMM "$$$$$$P dMM>;!!! 4MMMMMMb :::::.. "-=cczyycc??" .:::::::::MMMP <!!! dMMMb "?$$P" uMMM>;!!! 4MMMMMMMr`:::::::::.........:::::::::::::MMP';!!! ;MMMMMMn,.".uMMMMM ;!!! MMMMMMMMM,`::::::::::::::::::::::::::::::MM ;!!!! MMMMMMMMMMMMMMMMMM !!!! MMMMMMMMMb `:::::::::::::::::::::::::::::M" !!!! uMMMMMMMMMMMMMMMMMP !!! ;MMMMMMMMMMx :::::::::::::::::::::::::::::P.!!!! ,MMMMMMMMMMMMMMMMMM ,!!! MMMMMMMMMMMMx`::::::::::::::::::::::::::::!!!!> MMMMMMMMMMMMMMMMMMP !!!',MMMMMMMMMMMMM `:::::::::::::::::::::::::::*/int main() {int gx, gy, crystals, fee;std::cin >> gx >> gy >> crystals >> fee;std::vector<std::pair<std::pair<int, int>, int> > v(crystals);for (int i = 0; i < crystals; i++){int x, y, f;std::cin >> x >> y >> f;v[i] = { {x, y}, f };};long long dp[105][105][100];for (int i = 0; i <= 100; i++){for (int j = 0; j <= 100; j++){for (int k = 0; k < 100; k++){dp[i][j][k] = 10000000000;}}}for (int i = 0; i < 100; i++){dp[0][0][i] = 0;}for (int i = 0; i <= gy; i++){for (int j = 0; j <= gx; j++){dp[i + 1][j][0] = std::min(dp[i + 1][j][0], dp[i][j][0] + fee);dp[i][j + 1][0] = std::min(dp[i][j + 1][0], dp[i][j][0] + fee);for (int k = 0; k < crystals; k++) {dp[i][j][k + 1] = std::min(dp[i][j][k + 1], dp[i][j][k]);if (v[k].first.first + j <= gx && v[k].first.second + i <= gy) {dp[i + v[k].first.second][j + v[k].first.first][k + 1] = std::min(dp[i + v[k].first.second][j + v[k].first.first][k + 1],dp[i][j][k] + v[k].second);}}}}long long ans = dp[gy][gx][0];for (int i = 0; i < crystals; i++){ans = std::min(ans, dp[gy][gx][i + 1]);}std::cout << ans << std::endl;return 0;}