結果
問題 |
No.664 超能力者Aと株価予測
|
ユーザー |
|
提出日時 | 2021-05-30 03:02:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,374 bytes |
コンパイル時間 | 2,060 ms |
コンパイル使用メモリ | 195,044 KB |
最終ジャッジ日時 | 2025-01-21 20:43:50 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 5 WA * 10 |
ソースコード
#include <bits/stdc++.h> using namespace std; pair<long long int,long long int> dp[401][21][21]; int N, M, K; int A[401]; int main(void) { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> M >> K; for (int i = 0; i <= N; i++) { cin >> A[i]; } for (int i = 0; i <= N; i++) { for (int j = 0; j <= M; j++) { for (int k = 0; k <= M; k++) { dp[i][j][k].first = -1; dp[i][j][k].second = -1; } } } dp[0][0][0].first = K; dp[0][0][0].second = 0; for (int i = 0; i <= N; i++) { for (int j = 0; j <= M; j++) { for (int k = 0; k <= M; k++) { if (dp[i][j][k].first == -1) { continue; } if (dp[i + 1][j][k] < dp[i][j][k]) { dp[i + 1][j][k] = dp[i][j][k]; } if (j + 1 <= M) { long long int X = (dp[i][j][k].first) / A[i]; long long int cost = A[i] * X; long long int money = dp[i][j][k].first - cost; if (dp[i + 1][j + 1][k].first < money) { dp[i + 1][j + 1][k] = make_pair(money, X); } else if (dp[i + 1][j + 1][k].first == money) { if (dp[i + 1][j + 1][k].second < X) { dp[i + 1][j + 1][k] = make_pair(money, X); } } } if (k + 1 <= j) { long long int profit = A[i] * dp[i][j][k].second; long long int X = 0; long long int money = dp[i][j][k].first + profit; if (dp[i + 1][j][k + 1].first < money) { dp[i + 1][j][k + 1] = make_pair(money, X); } } } } } long long int res = 0; for (int i = 0; i <= M; i++) { for (int j = 0; j <= M; j++) { res = max(res, dp[N + 1][i][j].first); } } cout << res << '\n'; return 0; }