結果
問題 | No.496 ワープクリスタル (給料日前編) |
ユーザー |
|
提出日時 | 2017-03-24 22:53:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 1,519 bytes |
コンパイル時間 | 713 ms |
コンパイル使用メモリ | 93,516 KB |
実行使用メモリ | 7,552 KB |
最終ジャッジ日時 | 2024-07-05 22:17:05 |
合計ジャッジ時間 | 1,588 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#include<map> #include<set> #include<list> #include<cmath> #include<queue> #include<stack> #include<cstdio> #include<string> #include<vector> #include<complex> #include<cstdlib> #include<cstring> #include<numeric> #include<sstream> #include<iostream> #include<algorithm> #include<functional> #define mp make_pair #define pb push_back #define all(x) (x).begin(),(x).end() #define YES() printf("YES\n") #define NO() printf("NO\n") using namespace std; #define int long long //typedef long long ll; typedef unsigned long long ull; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<vb> vvb; typedef vector<vi> vvi; //typedef pair<int,int> P; const int INF=1e+13; const double EPS=1e-9; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; signed main(){ int gx,gy,n,f; int dp[51][101][101]; cin >> gx >> gy >> n >> f; for(int i = 0;i <= n;i++){ for(int j = 0;j <= gx;j++){ for(int k = 0;k <= gy;k++) dp[i][j][k] = INF; } } dp[0][0][0] = 0; for(int i = 0;i < n;i++){ int x,y,c; cin >> x >> y >> c; for(int j = 0;j <= gx;j++){ for(int k = 0;k <= gy;k++){ if(j + x <= gx && k + y <= gy){ dp[i + 1][j + x][k + y] = min(dp[i + 1][j + x][k + y],dp[i][j][k] + c); } dp[i + 1][j][k] = min(dp[i + 1][j][k],dp[i][j][k]); } } } int mi = INF; for(int i = 0;i <= gx;i++){ for(int j = 0;j <= gy;j++){ mi = min(mi,dp[n][i][j] + (gx + gy - i - j) * f); } } cout << mi << endl; return 0; }