結果
問題 | No.2693 Sword |
ユーザー |
|
提出日時 | 2024-03-22 22:23:21 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 7 ms / 2,000 ms |
コード長 | 4,737 bytes |
コンパイル時間 | 1,500 ms |
コンパイル使用メモリ | 139,284 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-09-30 11:55:05 |
合計ジャッジ時間 | 2,468 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <chrono>#include <cmath>#include <complex>#include <cstdint>#include <cstring>#include <ctime>#include <deque>#include <iomanip>#include <iostream>#include <iterator>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <stack>#include <unordered_map>#include <unordered_set>#include <vector>template <typename T1, typename T2>std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &p) {os << p.first << " " << p.second;return os;}template <typename T1, typename T2>std::istream &operator>>(std::istream &is, std::pair<T1, T2> &p) {is >> p.first >> p.second;return is;}template <typename T>std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {for (int i = 0; i < (int)v.size(); i++) {os << v[i] << (i + 1 != (int)v.size() ? " " : "");}return os;}template <typename T>std::istream &operator>>(std::istream &is, std::vector<T> &v) {for (T &in : v) is >> in;return is;}template <int mod>struct ModInt {int x;ModInt() : x(0) {}ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}ModInt &operator+=(const ModInt &p) {if ((x += p.x) >= mod) x -= mod;return *this;}ModInt &operator-=(const ModInt &p) {if ((x += mod - p.x) >= mod) x -= mod;return *this;}ModInt &operator*=(const ModInt &p) {x = (int)(1LL * x * p.x % mod);return *this;}ModInt &operator/=(const ModInt &p) {*this *= p.inverse();return *this;}ModInt &operator^=(long long p) { // quick_pow here:3ModInt res = 1;for (; p; p >>= 1) {if (p & 1) res *= *this;*this *= *this;}return *this = res;}ModInt operator-() const { return ModInt(-x); }ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }ModInt operator^(long long p) const { return ModInt(*this) ^= p; }bool operator==(const ModInt &p) const { return x == p.x; }bool operator!=(const ModInt &p) const { return x != p.x; }explicit operator int() const { return x; } // added by QCFiumModInt operator=(const int p) {x = p;return ModInt(*this);} // added by QCFiumModInt inverse() const {int a = x, b = mod, u = 1, v = 0, t;while (b > 0) {t = a / b;a -= t * b;std::swap(a, b);u -= t * v;std::swap(u, v);}return ModInt(u);}friend std::ostream &operator<<(std::ostream &os, const ModInt<mod> &p) {return os << p.x;}friend std::istream &operator>>(std::istream &is, ModInt<mod> &a) {long long x;is >> x;a = ModInt<mod>(x);return (is);}};using mint = ModInt<998244353>;const int MOD = 998244353;template <typename T>std::pair<std::vector<T>, std::vector<T>> get_prime_factor_with_kinds(T n) {std::vector<T> prime_factors;std::vector<T> cnt; // number of i_th factorfor (T i = 2; i * i <= n; i++) {if (n % i == 0) {prime_factors.push_back(i);cnt.push_back(0);while (n % i == 0) n /= i, cnt[(int)prime_factors.size() - 1]++;}}if (n > 1) prime_factors.push_back(n), cnt.push_back(1);assert(prime_factors.size() == cnt.size());return {prime_factors, cnt};}template <typename T>std::vector<T> get_divisors(T x, bool sorted = true) {std::vector<T> res;for (T i = 1; i <= x / i; i++)if (x % i == 0) {res.push_back(i);if (i != x / i) res.push_back(x / i);}if (sorted) std::sort(res.begin(), res.end());return res;}void solve() {unsigned long long up_bound = 1e18;long long n, p, k;std::cin >> n >> p >> k;std::vector<std::pair<int, unsigned long long>> a(n);std::cin >> a;std::vector dp(n + 1, std::vector(k + 1, 0ull));dp[0][0] = p;for (int i = 0; i < n; i++) {for (int j = 0; j <= k; j++) {auto [t, b] = a[i];dp[i + 1][j] = std::max(dp[i + 1][j], dp[i][j]);if (t == 1) {if (j + 1 <= k)dp[i + 1][j + 1] = std::max(dp[i + 1][j + 1], dp[i][j] + b);} else {if (j + 1 <= k)dp[i + 1][j + 1] = std::max(dp[i + 1][j + 1], dp[i][j] * 2);}if (dp[i + 1][j] > up_bound) {std::cout << -1 << '\n';return;}}}std::cout << dp[n][k] << std::endl;}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;// std::cin >> t;while (t--) {solve();}}