結果
問題 | No.496 ワープクリスタル (給料日前編) |
ユーザー |
|
提出日時 | 2017-12-02 15:45:37 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,019 bytes |
コンパイル時間 | 1,184 ms |
コンパイル使用メモリ | 158,972 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-28 03:36:54 |
合計ジャッジ時間 | 2,006 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 20 WA * 3 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define print(x) cout<<x<<endl; #define rep(i,a,b) for(int i=a;i<b;i++) #define REP(i,a) for(int i=0;i<a;i++) #define printall(n,array) for(int i=0;i<n;i++){cout<<array[i]<<" ";}cout<<endl; typedef long long ll; typedef pair<int, int> PI; typedef pair<int, PI> V; typedef vector<int> VE; const ll mod = 1000000007; //10^9+7 int dp[102][102]; bool flag[102][102]; int main(){ int X,Y,n,f; cin>>X>>Y>>n>>f; int x[52],y[52],c[52]; REP(i,n){ cin>>x[i]>>y[i]>>c[i]; } REP(i,X+1)REP(j,Y+1){ dp[i][j]=(i+j)*f; } int min_=mod; REP(i,X+1)REP(j,Y+1)flag[i][j]=false; REP(k,n){ if(c[k]>(x[k]+y[k])*f)continue; flag[0][0]=true; for(int i=X;i>=0;i--)for(int j=Y;j>=0;j--){ int xk=i+x[k]; int yk=j+y[k]; if(xk>X||yk>Y||flag[i][j]==false)continue; if(dp[xk][yk]>dp[i][j]+c[k]){ dp[xk][yk]=dp[i][j]+c[k]; flag[xk][yk]=true; min_=min(min_,dp[xk][yk]+(X+Y-xk-yk)*f); } } } print(min_); }