結果
問題 | 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;}