結果
問題 | No.496 ワープクリスタル (給料日前編) |
ユーザー |
![]() |
提出日時 | 2017-06-13 13:11:06 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 1,249 bytes |
コンパイル時間 | 481 ms |
コンパイル使用メモリ | 65,564 KB |
実行使用メモリ | 7,808 KB |
最終ジャッジ日時 | 2024-09-24 16:56:05 |
合計ジャッジ時間 | 1,356 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#include <iostream> #include <utility> #include <vector> #include <algorithm> typedef long long ll; using namespace std; int main(){ int gx,gy,n,f; cin >> gx >> gy >> n >> f; vector<pair<int, int>> dist(n); vector<int> c(n); for(int i=0;i<n;i++){ cin >> dist[i].first >> dist[i].second >> c[i]; } ll dp[53][103][103]; // for(int j=0;j<=gy;j++){ // dp[0][j][0] = j*f; // } // for(int i=0;i<=gx;i++){ // dp[0][0][i] = i*f; // } for(int i=0;i<=gx;i++){ for(int j=0;j<=gy;j++){ dp[0][i][j] = f*(i+j); } } for(int k=0;k<n;k++){ for(int i=0;i<=gx;i++){ for(int j=0;j<=gy;j++){ dp[k+1][i][j] = dp[k][i][j]; if(i < dist[k].first || j < dist[k].second){ // no way that we have used a crystal one step before. continue; }else{ dp[k+1][i][j] = min(dp[k][i-dist[k].first][j-dist[k].second]+c[k], dp[k+1][i][j]); } } } } // cout << endl; // for(int k=0;k<=n;k++){ // for(int j=gy;j>=0;j--){ // for(int i=0;i<=gx;i++){ // cout << dp[k][i][j] << " "; // } // cout << endl; // } // cout << endl; // } cout << dp[n][gx][gy] << endl; return 0; }