結果
問題 | No.496 ワープクリスタル (給料日前編) |
ユーザー |
![]() |
提出日時 | 2017-03-25 00:17:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 1,223 bytes |
コンパイル時間 | 877 ms |
コンパイル使用メモリ | 96,160 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-06 03:12:06 |
合計ジャッジ時間 | 1,653 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#if 1 #include <iostream> #include <fstream> #include <string> #include <vector> #include <map> #include <set> #include <unordered_map> #include <unordered_set> #include <queue> #include <stack> #include <array> #include <deque> #include <algorithm> #include <utility> #include <cstdint> #include <functional> #include <iomanip> #include <numeric> #define in std::cin #define out std::cout template<typename T> void fill_all(T& arr, const T& v) { arr = v; } template<typename T, typename ARR> void fill_all(ARR& arr, const T& v) { for (auto& i : arr) { fill_all(i, v); } } int Gx, Gy; int32_t N,F; int X[100]; int Y[100]; int C[100]; constexpr int INF = 1000000000; int32_t DP[101][101][51]; int32_t func(int x, int y, int i) { if (x > Gx || y > Gy) { return INF; } if (i == N) { return F*(Gx - x + Gy - y); } if (DP[x][y][i] != -1) { return DP[x][y][i]; } return DP[x][y][i] = std::min( func(x+X[i],y + Y[i],i+1) + C[i], func(x, y, i + 1) ) ; } int main() { using std::endl; in.sync_with_stdio(false); out.sync_with_stdio(false); fill_all(DP, -1); in >> Gx>>Gy>>N>>F; for (size_t i = 0; i < N; i++) { in >> X[i] >> Y[i] >> C[i]; } out << func(0, 0, 0) << endl; return 0; } #endif