結果
問題 | No.2693 Sword |
ユーザー |
|
提出日時 | 2024-03-22 23:40:36 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 10 ms / 2,000 ms |
コード長 | 869 bytes |
コンパイル時間 | 3,834 ms |
コンパイル使用メモリ | 265,036 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-09-30 12:45:40 |
合計ジャッジ時間 | 4,805 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
#include<bits/stdc++.h>#include <iostream>using namespace std;#include<atcoder/all>using namespace atcoder;using ll = long long;ll N,P,K;vector<ll> T,B;using Pll = pair<ll,ll>;ll next_P(ll P,ll T,ll B){if(T == 1) return min(P + B,1000'000'000'000'000'001ll);return min(P *2,1000'000'000'000'000'001ll);}void solve(){vector<vector<ll>> dp(N+1,vector<ll>(K+1,-1));dp[0][0] = P;for(ll i = 0;i<N;i++){for(ll j = 0;j<=K;j++){if(dp[i][j] == -1) continue;dp[i+1][j] = max(dp[i+1][j],dp[i][j]);if(j+1<=K)dp[i+1][j+1] = max(dp[i+1][j+1],next_P(dp[i][j],T[i],B[i]));}}ll ans = dp[N][K];if(ans>1'000'000'000'000'000'000) ans = -1;cout << ans << endl;}signed main(){cin.tie(nullptr);ios::sync_with_stdio(false);cin >> N >> P >> K;T.resize(N);B.resize(N);for(ll i=0;i<N;i++){cin >> T[i] >> B[i];}solve();}