結果
問題 | No.37 遊園地のアトラクション |
ユーザー |
![]() |
提出日時 | 2021-08-13 19:29:23 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,089 bytes |
コンパイル時間 | 3,254 ms |
コンパイル使用メモリ | 141,056 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-03 12:56:19 |
合計ジャッジ時間 | 4,047 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
#include <cassert>#include <cmath>#include <algorithm>#include <iostream>#include <iomanip>#include <limits.h>#include <map>#include <queue>#include <set>#include <string.h>#include <vector>using namespace std;typedef long long ll;int main() {int T;cin >> T;int N;cin >> N;int c;int C[N];memset(C, 0, sizeof(C));for (int i = 0; i < N; ++i) {cin >> C[i];}int v;int V[N][100];memset(V, 0, sizeof(V));for (int i = 0; i < N; ++i) {cin >> v;int k = 0;while (v > 0) {V[i][k] = v;v /= 2;++k;}}int dp[T + 1];memset(dp, -1, sizeof(dp));dp[0] = 0;int ans = 0;for (int i = 0; i < N; ++i) {for (int t = T - 1; t >= 0; --t) {if (dp[t] < 0) continue;int k = 0;int tv = 0;while (V[i][k] > 0) {tv += V[i][k];int nt = t + C[i] * (k + 1);if (T < nt) break;int nv = dp[t] + tv;dp[nt] = max(dp[nt], nv);ans = max(ans, dp[nt]);++k;}}}cout << ans << endl;return 0;}