結果
問題 | No.2693 Sword |
ユーザー |
![]() |
提出日時 | 2024-03-22 21:43:27 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,125 bytes |
コンパイル時間 | 2,155 ms |
コンパイル使用メモリ | 206,604 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-09-30 11:11:59 |
合計ジャッジ時間 | 3,390 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h>#define int llusing namespace std;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define rng(i,c,n) for(int i=c;i<n;i++)#define fi first#define se second#define pb push_back#define all(a) a.begin(), a.end()#define sz(a) ((int) a.size())#define vec(...) vector<__VA_ARGS__>#define _4ab8goq ios::sync_with_stdio(0),cin.tie(0);typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pii;void print(){cout<<'\n';}template<class h,class...t>void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}void chmax(int&a,int b){a=max(a,b);}void chmin(int&a,int b){a=min(a,b);}void slv(){int n,p,k;cin>>n>>p>>k;vec(pii) a(n);rep(i,n){cin>>a[i].fi>>a[i].se;}int inf=1e18;inf+=1;vi dp(k+1,-inf);dp[0]=p;rep(i,n){auto [t,b]=a[i];auto ndp=dp;rep(j,k){if(dp[j]==-inf) continue;if(t==1){chmax(ndp[j+1],min(inf,dp[j]+b));}else{chmax(ndp[j+1],min(inf,dp[j]*2));}}dp.swap(ndp);}// print(dp[k]);if(dp[k]==inf) dp[k]=-1;cout<<dp[k]<<"\n";}signed main(){_4ab8goq;slv();}