// {{{ //#pragma GCC optimize("O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define VARGS_(_4, _3, _2, _1, N, ...) N #define VARGS(...) VARGS_(__VA_ARGS__, 4, 3, 2, 1) #define CONCAT_(a, b) a##b #define CONCAT(a, b) CONCAT_(a, b) #define FOR_1(x) for (auto& x) #define FOR_2(i, n) for (auto i = remove_reference_t<decltype(n)>{0}; i < (n); ++i) #define FOR_3(i, b, e) for (auto i = remove_reference_t<decltype(e)>{b}; i < (e); ++i) #define FOR_4(i, b, e, s) for (auto i = remove_reference_t<decltype(e)>{b}; i < (e); i += s) #define FORD_2(i, n) for (auto i = (n) - 1; i >= 0; --i) #define FORD_3(i, b, e) for (auto i = remove_reference_t<decltype(b)>{(e) - 1}; i >= (b); --i) #define FORD_4(i, b, e, s) for (auto i = remove_reference_t<decltype(b)>{(e) - 1}; i >= (b); i -= s) #define FOR(...) CONCAT(FOR_, VARGS(__VA_ARGS__))(__VA_ARGS__) #define FORD(...) CONCAT(FORD_, VARGS(__VA_ARGS__))(__VA_ARGS__) #define B begin() #define E end() #define RB rbegin() #define RE rend() #define A(x) std::begin(x), std::end(x) #define RA(x) std::rbegin(x), std::rend(x) #define RANGE(x, b, e) (std::begin(x) + (b)), (std::begin(x) + (e)) #define MP make_pair #define MT make_tuple #define FS first #define ND second #define G1 get<0> #define G2 get<1> #define G3 get<2> #define G4 get<3> #define G5 get<4> #define PB push_back #define PP pop_back #define PF push_front #define FF pop_front #define RS resize #define INF(T) numeric_limits<T>::max() #define L0(_expr) [&]() { return _expr; } #define L1(_expr) [&](auto&& _1) { return _expr; } #define L2(_expr) [&](auto&& _1, auto&& _2) { return _expr; } #define _ CONCAT(_unused_, __COUNTER__) #define MIN min_element #define MAX max_element #define SUM accumulate using namespace std; using LL = long long; using LD = long double; using ULL = unsigned long long; template<class T1,class T2> using P = pair<T1,T2>; using PII = P<int,int>; using PLL = P<LL,LL>; using PLD = P<LD,LD>; template<class T> using V = vector<T>; using VI = V<int>; using VLL = V<LL>; using VLD = V<LD>; using VB = V<bool>; using VS = V<string>; template<class T,class Comp=greater<T>> using PQ = priority_queue<T,V<T>,Comp>; template<class T> int sz(const T& x) { return size(x); } template<class T> bool amin(T& a, const T& b) { if (b < a) { a = b; return true; } return false; } template<class T> bool amax(T& a, const T& b) { if (b > a) { a = b; return true; } return false; } /* find_by_order(k) - k'th largest counting from 0; order_of_key(k) - number of items strictly smaller than k; join(other), split(k, other) - all keys in other greater than in *(this). */ template<class K,class V,class Comp=less<K>> using ordered_map = __gnu_pbds::tree<K,V,Comp, __gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; template<class T,class Comp=less<T>> using ordered_set = ordered_map<T,__gnu_pbds::null_type,Comp>; //const size_t rseed = std::chrono::high_resolution_clock::now().time_since_epoch().count(); //mt19937 _rnd(rseed); template<class T> T randint(T lo, T hi) { return uniform_int_distribution<T>{lo,hi}(_rnd); } //struct random_hash { // template<class T1,class T2> size_t operator()(const P<T1,T2>& key) const noexcept { // size_t h1 = hash<T1>{}(key.FS), h2 = hash<T2>{}(key.ND); // return (*this)(h1 + 0x517cc1b7 + (h2 << 6) + (h2 >> 2)); } // template<class T> size_t operator()(const T& key) const noexcept { // size_t h = hash<T>{}(key); return h + (h << 4) + 0x9e3779b9 + (rseed << 6) + (rseed >> 2); }}; //template<class K,class V> using hash_map = __gnu_pbds::gp_hash_table<K,V,random_hash>; //template<class T> using hash_set = hash_map<T,__gnu_pbds::null_type>; string _sep = " ", _ignore; bool _newline = true; stack<ostream*> _ostack; stack<istream*> _istack; template<class TH> void out(const TH& h) { if (_newline) _newline = false; else *_ostack.top() << _sep; *_ostack.top() << h; } template<class TH,class...TA> void out(const TH& h, const TA&... a) { out(h); out(a...); } void outln() { *_ostack.top() << '\n'; _newline = true; } template<class...TA> void outln(const TA&... a) { out(a...); outln(); } template<class TH> void in(TH& h) { *_istack.top() >> h; } template<class TH,class...TA> void in(TH& h, TA&... a) { in(h); in(a...); } template<class...TA> void EXIT(const TA&... a) { outln(a...); exit(0); } #ifdef SPONGE template<class...TA> void dbg(const TA&... a) { _ostack.push(&cerr); cerr << "\033[1;33m"; outln(a...); cerr << "\033[0m"; _ostack.pop(); } #else #define dbg(...) #endif struct _upgrade_io { _upgrade_io(bool ok) { _ostack.push(&cout); _istack.push(&cin); if (ok) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed, ios::floatfield); }} } _upgrade_io(true); /* bitset: _Find_first(), _Find_next(i) */ // }}} int n, k, ans = INF(int); int dp[2001][2001]; int main() { in(n, k); dp[0][0] = 1; FOR(i, 1, n) { dp[i][0] = i + 1; dp[i][i] = i + 1; FOR(j, 1, i) { dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + 1; if (i > 1) dp[i][j] -= dp[i - 2][j - 1]; } } FOR(i, n) FOR(j, i + 1) { int a; in(a); if (dp[i][j] <= k) amin(ans, a); } outln(ans); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 | // {{{ //#pragma GCC optimize("O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define VARGS_(_4, _3, _2, _1, N, ...) N #define VARGS(...) VARGS_(__VA_ARGS__, 4, 3, 2, 1) #define CONCAT_(a, b) a##b #define CONCAT(a, b) CONCAT_(a, b) #define FOR_1(x) for (auto& x) #define FOR_2(i, n) for (auto i = remove_reference_t<decltype(n)>{0}; i < (n); ++i) #define FOR_3(i, b, e) for (auto i = remove_reference_t<decltype(e)>{b}; i < (e); ++i) #define FOR_4(i, b, e, s) for (auto i = remove_reference_t<decltype(e)>{b}; i < (e); i += s) #define FORD_2(i, n) for (auto i = (n) - 1; i >= 0; --i) #define FORD_3(i, b, e) for (auto i = remove_reference_t<decltype(b)>{(e) - 1}; i >= (b); --i) #define FORD_4(i, b, e, s) for (auto i = remove_reference_t<decltype(b)>{(e) - 1}; i >= (b); i -= s) #define FOR(...) CONCAT(FOR_, VARGS(__VA_ARGS__))(__VA_ARGS__) #define FORD(...) CONCAT(FORD_, VARGS(__VA_ARGS__))(__VA_ARGS__) #define B begin() #define E end() #define RB rbegin() #define RE rend() #define A(x) std::begin(x), std::end(x) #define RA(x) std::rbegin(x), std::rend(x) #define RANGE(x, b, e) (std::begin(x) + (b)), (std::begin(x) + (e)) #define MP make_pair #define MT make_tuple #define FS first #define ND second #define G1 get<0> #define G2 get<1> #define G3 get<2> #define G4 get<3> #define G5 get<4> #define PB push_back #define PP pop_back #define PF push_front #define FF pop_front #define RS resize #define INF(T) numeric_limits<T>::max() #define L0(_expr) [&]() { return _expr; } #define L1(_expr) [&](auto&& _1) { return _expr; } #define L2(_expr) [&](auto&& _1, auto&& _2) { return _expr; } #define _ CONCAT(_unused_, __COUNTER__) #define MIN min_element #define MAX max_element #define SUM accumulate using namespace std; using LL = long long; using LD = long double; using ULL = unsigned long long; template<class T1,class T2> using P = pair<T1,T2>; using PII = P<int,int>; using PLL = P<LL,LL>; using PLD = P<LD,LD>; template<class T> using V = vector<T>; using VI = V<int>; using VLL = V<LL>; using VLD = V<LD>; using VB = V<bool>; using VS = V<string>; template<class T,class Comp=greater<T>> using PQ = priority_queue<T,V<T>,Comp>; template<class T> int sz(const T& x) { return size(x); } template<class T> bool amin(T& a, const T& b) { if (b < a) { a = b; return true; } return false; } template<class T> bool amax(T& a, const T& b) { if (b > a) { a = b; return true; } return false; } /* find_by_order(k) - k'th largest counting from 0; order_of_key(k) - number of items strictly smaller than k; join(other), split(k, other) - all keys in other greater than in *(this). */ template<class K,class V,class Comp=less<K>> using ordered_map = __gnu_pbds::tree<K,V,Comp, __gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; template<class T,class Comp=less<T>> using ordered_set = ordered_map<T,__gnu_pbds::null_type,Comp>; //const size_t rseed = std::chrono::high_resolution_clock::now().time_since_epoch().count(); //mt19937 _rnd(rseed); template<class T> T randint(T lo, T hi) { return uniform_int_distribution<T>{lo,hi}(_rnd); } //struct random_hash { // template<class T1,class T2> size_t operator()(const P<T1,T2>& key) const noexcept { // size_t h1 = hash<T1>{}(key.FS), h2 = hash<T2>{}(key.ND); // return (*this)(h1 + 0x517cc1b7 + (h2 << 6) + (h2 >> 2)); } // template<class T> size_t operator()(const T& key) const noexcept { // size_t h = hash<T>{}(key); return h + (h << 4) + 0x9e3779b9 + (rseed << 6) + (rseed >> 2); }}; //template<class K,class V> using hash_map = __gnu_pbds::gp_hash_table<K,V,random_hash>; //template<class T> using hash_set = hash_map<T,__gnu_pbds::null_type>; string _sep = " ", _ignore; bool _newline = true; stack<ostream*> _ostack; stack<istream*> _istack; template<class TH> void out(const TH& h) { if (_newline) _newline = false; else *_ostack.top() << _sep; *_ostack.top() << h; } template<class TH,class...TA> void out(const TH& h, const TA&... a) { out(h); out(a...); } void outln() { *_ostack.top() << '\n'; _newline = true; } template<class...TA> void outln(const TA&... a) { out(a...); outln(); } template<class TH> void in(TH& h) { *_istack.top() >> h; } template<class TH,class...TA> void in(TH& h, TA&... a) { in(h); in(a...); } template<class...TA> void EXIT(const TA&... a) { outln(a...); exit(0); } #ifdef SPONGE template<class...TA> void dbg(const TA&... a) { _ostack.push(&cerr); cerr << "\033[1;33m"; outln(a...); cerr << "\033[0m"; _ostack.pop(); } #else #define dbg(...) #endif struct _upgrade_io { _upgrade_io(bool ok) { _ostack.push(&cout); _istack.push(&cin); if (ok) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed, ios::floatfield); }} } _upgrade_io(true); /* bitset: _Find_first(), _Find_next(i) */ // }}} int n, k, ans = INF(int); int dp[2001][2001]; int main() { in(n, k); dp[0][0] = 1; FOR(i, 1, n) { dp[i][0] = i + 1; dp[i][i] = i + 1; FOR(j, 1, i) { dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + 1; if (i > 1) dp[i][j] -= dp[i - 2][j - 1]; } } FOR(i, n) FOR(j, i + 1) { int a; in(a); if (dp[i][j] <= k) amin(ans, a); } outln(ans); } |