結果
問題 | No.2693 Sword |
ユーザー |
![]() |
提出日時 | 2024-03-22 21:46:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 1,067 bytes |
コンパイル時間 | 2,398 ms |
コンパイル使用メモリ | 200,092 KB |
最終ジャッジ日時 | 2025-02-20 11:31:05 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h> using namespace std; long long INF = 1000000000000000001; int main() { int n, k; long long p; cin >> n >> p >> k; vector<int> t(n); vector<long long> b(n); for (int i = 0; i < n; i++) { cin >> t[i] >> b[i]; } //dp[i][j] := i番目まで見て、装備をk個使った状態 vector<vector<long long>> dp(n + 1, vector<long long>(k + 1)); dp[0][0] = p; for (int i = 0; i < n; i++) { for (int j = 0; j <= k; j++) { dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]); if (j == k) { continue; } if (dp[i][j] == 0LL) { continue; } if (t[i] == 1) { long long x = min(INF, dp[i][j] + b[i]); dp[i + 1][j + 1] = max(dp[i + 1][j + 1], x); } else { long long x = min(INF, dp[i][j] * 2LL); dp[i + 1][j + 1] = max(dp[i + 1][j + 1], x); } } } cout << (dp[n][k] == INF ? -1 : dp[n][k]) << endl; }