結果
問題 | No.37 遊園地のアトラクション |
ユーザー |
![]() |
提出日時 | 2015-11-27 02:42:41 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 839 bytes |
コンパイル時間 | 1,303 ms |
コンパイル使用メモリ | 160,352 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-10 13:08:33 |
合計ジャッジ時間 | 2,325 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
#define _CRT_SECURE_NO_WARNINGS#include "bits/stdc++.h"#define rep(i,n) for(int i = 0;i < n;i++)#define P(p) cout<<(p)<<endl;using namespace std;typedef long long ll;int dx[] = { 0, 1, 0, -1 };int dy[] = { -1, 0, 1, 0 };int sttoi(std::string str) {int ret;std::stringstream ss; ss << str;ss >> ret;return ret;}ll gcd(ll a, ll b){if (b > a)swap(a, b); if (b == 0)return a; else{ return gcd(b, a%b); }}void solve() {int t, n, c[15],v[15];int dp[10500];rep(i, 10500)dp[i] = 0;cin >> t >> n;rep(i, n)cin >> c[i];rep(i, n)cin >> v[i];for (int i = 0; i < n ; i++){while (v[i] > 0){for (int j = t; j >= 0; j--){dp[j + c[i]] = max(dp[j + c[i]], dp[j] + v[i]);}v[i] /= 2;}}int maxi = -1;rep(i, t + 1){maxi = max(maxi, dp[i]);}P(maxi);}int main() {solve();return 0;}