結果
問題 | No.2693 Sword |
ユーザー |
|
提出日時 | 2024-03-22 21:35:28 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 3,079 bytes |
コンパイル時間 | 4,763 ms |
コンパイル使用メモリ | 264,556 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-09-30 11:01:17 |
合計ジャッジ時間 | 4,731 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;// typetypedef long long ll;typedef long double ld;using i128 = __int128_t;template<class T> using pq = priority_queue<T>;template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;template<class T> using v = vector<T>;#define V vector#define pl pair<ll, ll>#define vl v<ll>#define vp v<pl>#define vm v<mint>// IN-OUT#define NYAN ios::sync_with_stdio(false);cin.tie(nullptr);cout<<fixed<<setprecision(15);ostream &operator<<(ostream &os, const i128 &v) {if(v == 0) { return (os << "0"); }i128 num = v;if(v < 0) { os << '-'; num = -num; }string s;for(; num > 0; num /= 10) { s.push_back((char)(num % 10) + '0'); }reverse(s.begin(), s.end());return (os << s);}void Yes(bool b=1) { cout << ( b == 1 ? "Yes" : "No" ) << "\n"; }void YES(bool b=1) { cout << ( b == 1 ? "YES" : "NO" ) << "\n"; }void No(bool b=1) { cout << ( b == 1 ? "No" : "Yes" ) << "\n"; }void NO(bool b=1) { cout << ( b == 1 ? "NO" : "YES" ) << "\n"; }void CIN() {}template <typename T, class... U> void CIN(T &t, U &...u) { cin >> t; CIN(u...); }void COUT() { cout << "\n"; }template <typename T, class... U, char sep = ' '> void COUT(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << sep; COUT(u...); }#define dump(x) cerr << #x << ":"<< x << "\n";#define vdump(x) rep(repeat, sz(x)) cerr << repeat << ":" << x[repeat] << "\n";// macro#define bp __builtin_popcountll#define ALL(x) x.begin(),x.end()#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)#define reps(i, s, n) for (ll i = s; i < (ll)(n); i++)#define sz(x) (ll)x.size()ll xd[]={0, 1, 0, -1, 1, 1, -1, -1};ll yd[]={1, 0, -1, 0, 1, -1, -1, 1};// functiontemplate<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }template<typename T>int bl(T x) { int s = 0; while(x) {x >>= 1; s++;} return s; } // bitlengthll rmax(ll a, ll b){return max(a, b);}ll rmin(ll a, ll b){return min(a, b);}ll rsum(ll a, ll b){return a + b;}ll rzero(){return 0;}// constantlong double PI = 3.14159265358979;#define INF32 2147483647#define INF64 9223372036854775807#define INF 922337203685477580using mint = modint998244353;// using mint = modint1000000007;/* SOLVE BEGIN ************************************************************************** */void solve(){ll n, s, k;cin >> n >> s >> k;vl t(n), b(n);rep(i, n) cin >> t[i] >> b[i];vl dp(k + 1, -1);const ll d = 1e18;dp[0] = s;rep(i, n){vl tmp = dp;rep(j, k){if(dp[j] == -1) continue;if(t[i] == 1){chmax(tmp[j + 1], dp[j] + b[i]);}else{i128 nx = dp[j] * (i128)2;if(nx > d) nx = d + 1;chmax(tmp[j + 1], (ll)nx);}chmin(tmp[j + 1], d + 1);}swap(dp, tmp);}if(dp[k] > d) cout << -1 << "\n";else cout << dp[k] << "\n";}int main(){NYANsolve();return 0;}