結果
問題 | No.496 ワープクリスタル (給料日前編) |
ユーザー |
![]() |
提出日時 | 2017-03-24 22:37:19 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 756 bytes |
コンパイル時間 | 1,244 ms |
コンパイル使用メモリ | 159,264 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-06 03:13:00 |
合計ジャッジ時間 | 1,814 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#include<bits/stdc++.h> using namespace std; const int INF = 1 << 30; void chmin(int &a, int b) { a = min(a, b); } int main() { int Gx, Gy, N, F; int x[50], y[50], z[50]; cin >> Gx >> Gy >> N >> F; for(int i = 0; i < N; i++) { cin >> x[i] >> y[i] >> z[i]; } int dp[203][203]; fill_n(*dp, 203 * 203, INF); dp[0][0] = 0; for(int k = 0; k < N; k++) { for(int i = Gx; i >= 0; i--) { for(int j = Gy; j >= 0; j--) { chmin(dp[i + x[k]][j + y[k]], dp[i][j] + z[k]); } } } int ret = F * (Gx + Gy); for(int i = 0; i <= Gx; i++) { for(int j = 0; j <= Gy; j++) { if(dp[Gx - i][Gy - j] == INF) continue; ret = min(ret, F * (i + j) + dp[Gx - i][Gy - j]); } } cout << ret << endl; }