結果
問題 | No.37 遊園地のアトラクション |
ユーザー |
|
提出日時 | 2020-05-31 20:15:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 5,000 ms |
コード長 | 1,190 bytes |
コンパイル時間 | 1,657 ms |
コンパイル使用メモリ | 174,844 KB |
実行使用メモリ | 8,576 KB |
最終ジャッジ日時 | 2024-10-10 13:40:45 |
合計ジャッジ時間 | 2,660 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef long double ld;#define rep(i,n) for (int i = 0; i < (n); ++i)template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }const ll INF=1LL<<60;const int inf=(1<<30)-1;const int mod=1e9+7;int dx[8]={1,0,-1,0,-1,-1,1,1};int dy[8]={0,1,0,-1,-1,1,-1,1};int main(){cin.tie(0);ios::sync_with_stdio(false);int t,n;cin >> t >> n;vector<int> c(n),v(n);rep(i,n){cin >> c[i];}rep(i,n){cin >> v[i];}vector<pair<int,int>> a;rep(i,n){while(v[i]){a.push_back({c[i],v[i]});v[i]/=2;}}int m=a.size();vector<vector<int>> dp(m+1,vector<int>(t+1,-1));dp[0][0]=0;for(int i=0;i<m;i++){for(int j=0;j<=t;j++){chmax(dp[i+1][j],dp[i][j]);if(j+a[i].first<=t){chmax(dp[i+1][j+a[i].first],dp[i][j]+a[i].second);}}}int ans=0;rep(i,t+1){chmax(ans,dp[m][i]);}cout << ans << endl;}