結果
問題 | No.158 奇妙なお使い |
ユーザー |
![]() |
提出日時 | 2014-11-12 19:23:14 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 48 ms / 5,000 ms |
コード長 | 2,155 bytes |
コンパイル時間 | 874 ms |
コンパイル使用メモリ | 87,292 KB |
実行使用メモリ | 46,896 KB |
最終ジャッジ日時 | 2024-06-28 21:50:54 |
合計ジャッジ時間 | 3,335 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
#include <algorithm>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#include <functional>#include <iostream>#include <map>#include <memory>#include <queue>#include <set>#include <sstream>#include <stack>#include <string>#include <utility>#include <vector>using namespace std;#define sz size()#define pb push_back#define mp make_pair#define fi first#define se second#define all(c) (c).begin(), (c).end()#define rep(i,a,b) for(int i=(a);i<(b);++i)#define clr(a, b) memset((a), (b) ,sizeof(a))#define MOD 1000000009int dp[10001][11][101];int f1(int a0, int a1, int a2, int db, int b0, int b1, int b2, int dc, int c0, int c1, int c2){clr(dp,-1);dp[0][a0][a1]=a2;int mx = 0;rep(i,1,10000){rep(j,0,11){rep(k,0,101){if(dp[i-1][j][k] != -1){// bint d = db;int d0 = min(j,d/1000);d -= d0*1000;int d1 = min(k,d/100);d -= d1*100;if(d <= dp[i-1][j][k]){dp[i][j-d0+b0][k-d1+b1] = max(dp[i][j-d0+b0][k-d1+b1], dp[i-1][j][k]-d+b2);mx = max(mx,i);}int e = dc;int e0 = min(j,e/1000);e -= e0*1000;int e1 = min(k,e/100);e -= e1*100;if(e <= dp[i-1][j][k]){dp[i][j-e0+c0][k-e1+c1] = max(dp[i][j-e0+c0][k-e1+c1], dp[i-1][j][k]-e+c2);mx = max(mx,i);}}}}}return mx;}int main(){int a0,a1,a2;int db,b0,b1,b2;int dc,c0,c1,c2;cin>>a0>>a1>>a2;cin>>db;cin>>b0>>b1>>b2;cin>>dc;cin>>c0>>c1>>c2;cout << f1(a0,a1,a2,db,b0,b1,b2,dc,c0,c1,c2) << endl;return 0;}/*想定は動的計画法です。dp[回数][1000円札の数][100円玉の数]=1円玉の最大個数でできると思います。テストケースは貪欲が通らないように工夫したつもりですが、動的計画法以外でも通ってしまったらごめんなさい。*/