結果

問題 No.2693 Sword
コンテスト
ユーザー VvyLw
提出日時 2024-03-22 22:46:35
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 4,247 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,178 ms
コンパイル使用メモリ 99,004 KB
実行使用メモリ 19,072 KB
最終ジャッジ日時 2024-09-30 12:10:54
合計ジャッジ時間 1,936 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#line 1 "a.cpp"
#include <vector>
#line 2 "/home/huitloxopetl/CP_Library/C++/core/io/output.hpp"

#include <iostream>
#line 5 "/home/huitloxopetl/CP_Library/C++/core/io/output.hpp"
#include <utility>
#include <map>
#include <set>
#include <deque>
#ifndef TEMPLATE
using i128 = __int128_t;
using u128 = __uint128_t;
#endif
namespace IO {
std::ostream &operator<<(std::ostream &dest, const i128 &value) {
    std::ostream::sentry s(dest);
    if(s) {
        u128 tmp = value < 0 ? -value : value;
        char buffer[128];
        char *d = std::end(buffer);
        do {
            --d;
            *d = "0123456789"[tmp % 10];
            tmp /= 10;
        } while(tmp != 0);
        if(value < 0) {
            --d;
            *d = '-';
        }
        int len = std::end(buffer) - d;
        if(dest.rdbuf() -> sputn(d, len) != len) {
            dest.setstate(std::ios_base::badbit);
        }
    }
    return dest;
}
template <class T, class U> std::ostream& operator<<(std::ostream &os, const std::pair<T, U> &p){ os << p.first << ' ' << p.second; return os; }
template <class T, size_t N> std::ostream& operator<<(std::ostream &os, const std::array<T, N> &a){ if(a.size()){ os << a.front(); for(auto i=a.begin(); ++i!=a.end();){ os << ' ' << *i; } } return os; }
template <class T> std::ostream& operator<<(std::ostream &os, const std::vector<T> &v){ if(v.size()){ os << v.front(); for(auto i=v.begin(); ++i!=v.end();){ os << ' ' << *i; } } return os; }
template <class K, class V> std::ostream& operator<<(std::ostream &os, const std::map<K, V> &m){ if(m.size()){ os << m.begin()->first << ' ' << m.begin()->second; for(auto i=m.begin(); ++i!=m.end();){ os << '\n' << i->first << ' ' << i->second; } } return os; }
template <class T> std::ostream& operator<<(std::ostream &os, const std::set<T> &st){ if(st.size()){ os << *st.begin(); for(auto i=st.begin(); ++i!=st.end();){ os << ' ' << *i; } } return os; }
template <class T> std::ostream& operator<<(std::ostream &os, const std::multiset<T> &ms){ if(ms.size()){ os << *ms.begin(); for(auto i=ms.begin(); ++i!=ms.end();){ os << ' ' << *i; } } return os; }
template <class T> std::ostream& operator<<(std::ostream &os, const std::deque<T> &dq){ if(dq.size()){ os << dq.front(); for(auto i=dq.begin(); ++i!=dq.end();){ os << ' ' << *i; } } return os; }
inline void out(){ std::cout << '\n'; }
template <bool flush=false, class T> inline void out(const T& x){ std::cout << x << '\n'; if(flush) std::cout.flush(); }
template <bool flush=false, class Head, class... Tail> inline void out(const Head& head, const Tail&... tail){ std::cout << head << ' '; out<flush>(tail...); }
template <bool flush=false, class T> inline void vout(const T& v){ std::cout << v << '\n'; if(flush) std::cout.flush(); }
template <bool flush=false, class T> inline void vout(const std::vector<T>& v){ for(const auto &el: v) std::cout << el << '\n'; if(flush) std::cout.flush(); }
template <bool flush=false, class Head, class... Tail> inline void vout(const Head& head, const Tail&... tail){ std::cout << head << '\n'; vout<flush>(tail...); }

#define fin(...) do{ out(__VA_ARGS__); return; }while(false)
} // IO

#if local
//https://gist.github.com/naskya/1e5e5cd269cfe16a76988378a60e2ca3
#include <C++/core/io/debug_print.hpp>
#else
#define dump(...) static_cast<void>(0)
#endif

/**
 * @brief 出力
 */
#line 3 "a.cpp"
using namespace IO;
template <class T, class U> inline bool chmax(T& a, const U& b) {
	if(a < b) {
		a = b;
		return true;
	}
	return false;
}
int main() {
	std::cin.tie(nullptr) -> sync_with_stdio(false);
	int n, k;
	int64_t p;
	std::cin >> n >> p >> k;
	const auto chk = [](const __int128_t x) -> bool { return x > int64_t(1e18); };
	std::vector dp(n + 1, std::vector(k + 1, __int128_t(0)));
	dp[0][0] = p;
	for(int i = 0; i < n; ++i) {
		int t, b;
		std::cin >> t >> b;
		for(int j = 0; j < k; ++j) {
			if(t == 1) {
				const auto x = dp[i][j] + b;
				if(chk(x)) {
					std::cout << -1 << '\n';
					std::exit(0);
				}
				chmax(dp[i + 1][j + 1], x);
			} else {
				const auto x = dp[i][j] * 2;
				if(chk(x)) {
					std::cout << -1 << '\n';
					std::exit(0);
				}
				chmax(dp[i + 1][j + 1], x);
			}
			chmax(dp[i + 1][j], dp[i][j]);
		}
	}
	std::cout << dp[n][k] << '\n';
}
0