結果
問題 | No.1460 Max of Min |
ユーザー | KoD |
提出日時 | 2021-03-31 22:26:57 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 663 ms / 2,000 ms |
コード長 | 3,798 bytes |
コンパイル時間 | 2,272 ms |
コンパイル使用メモリ | 207,260 KB |
実行使用メモリ | 11,128 KB |
最終ジャッジ日時 | 2023-08-22 02:45:34 |
合計ジャッジ時間 | 33,593 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 494 ms
10,876 KB |
testcase_04 | AC | 495 ms
11,128 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 495 ms
10,940 KB |
testcase_07 | AC | 510 ms
10,924 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 663 ms
10,956 KB |
testcase_11 | AC | 552 ms
10,960 KB |
testcase_12 | AC | 79 ms
4,596 KB |
testcase_13 | AC | 451 ms
10,184 KB |
testcase_14 | AC | 117 ms
5,656 KB |
testcase_15 | AC | 53 ms
4,380 KB |
testcase_16 | AC | 353 ms
9,888 KB |
testcase_17 | AC | 201 ms
6,960 KB |
testcase_18 | AC | 5 ms
4,380 KB |
testcase_19 | AC | 166 ms
6,452 KB |
testcase_20 | AC | 9 ms
4,376 KB |
testcase_21 | AC | 23 ms
4,376 KB |
testcase_22 | AC | 174 ms
6,700 KB |
testcase_23 | AC | 5 ms
4,376 KB |
testcase_24 | AC | 227 ms
7,732 KB |
testcase_25 | AC | 4 ms
4,376 KB |
testcase_26 | AC | 417 ms
10,664 KB |
testcase_27 | AC | 57 ms
4,380 KB |
testcase_28 | AC | 17 ms
4,380 KB |
testcase_29 | AC | 206 ms
7,224 KB |
testcase_30 | AC | 380 ms
10,132 KB |
testcase_31 | AC | 183 ms
6,912 KB |
testcase_32 | AC | 287 ms
9,396 KB |
testcase_33 | AC | 92 ms
5,064 KB |
testcase_34 | AC | 138 ms
6,172 KB |
testcase_35 | AC | 48 ms
4,376 KB |
testcase_36 | AC | 19 ms
4,380 KB |
testcase_37 | AC | 179 ms
7,172 KB |
testcase_38 | AC | 320 ms
9,596 KB |
testcase_39 | AC | 101 ms
5,360 KB |
testcase_40 | AC | 71 ms
4,596 KB |
testcase_41 | AC | 51 ms
4,380 KB |
testcase_42 | AC | 29 ms
4,376 KB |
testcase_43 | AC | 157 ms
6,744 KB |
testcase_44 | AC | 282 ms
9,088 KB |
testcase_45 | AC | 10 ms
4,376 KB |
testcase_46 | AC | 119 ms
5,884 KB |
testcase_47 | AC | 171 ms
6,684 KB |
testcase_48 | AC | 345 ms
9,592 KB |
testcase_49 | AC | 215 ms
7,740 KB |
testcase_50 | AC | 14 ms
4,380 KB |
testcase_51 | AC | 169 ms
7,136 KB |
testcase_52 | AC | 41 ms
4,380 KB |
testcase_53 | AC | 188 ms
7,292 KB |
testcase_54 | AC | 406 ms
10,952 KB |
testcase_55 | AC | 399 ms
10,916 KB |
testcase_56 | AC | 402 ms
11,072 KB |
testcase_57 | AC | 391 ms
10,872 KB |
testcase_58 | AC | 499 ms
10,948 KB |
testcase_59 | AC | 386 ms
10,948 KB |
testcase_60 | AC | 355 ms
10,996 KB |
testcase_61 | AC | 357 ms
10,980 KB |
testcase_62 | AC | 373 ms
11,116 KB |
testcase_63 | AC | 351 ms
10,920 KB |
testcase_64 | AC | 348 ms
10,972 KB |
testcase_65 | AC | 397 ms
10,940 KB |
testcase_66 | AC | 382 ms
10,920 KB |
testcase_67 | AC | 384 ms
10,940 KB |
testcase_68 | AC | 417 ms
10,920 KB |
testcase_69 | AC | 407 ms
10,948 KB |
testcase_70 | AC | 420 ms
11,128 KB |
testcase_71 | AC | 426 ms
10,976 KB |
testcase_72 | AC | 397 ms
10,908 KB |
testcase_73 | AC | 403 ms
10,912 KB |
testcase_74 | AC | 399 ms
10,884 KB |
testcase_75 | AC | 478 ms
10,916 KB |
testcase_76 | AC | 395 ms
10,656 KB |
testcase_77 | AC | 393 ms
10,868 KB |
testcase_78 | AC | 369 ms
10,972 KB |
testcase_79 | AC | 405 ms
10,656 KB |
testcase_80 | AC | 385 ms
10,688 KB |
testcase_81 | AC | 376 ms
10,888 KB |
testcase_82 | AC | 371 ms
10,676 KB |
testcase_83 | AC | 384 ms
10,892 KB |
testcase_84 | AC | 502 ms
10,856 KB |
testcase_85 | AC | 583 ms
10,664 KB |
testcase_86 | AC | 583 ms
10,684 KB |
testcase_87 | AC | 495 ms
10,872 KB |
testcase_88 | AC | 532 ms
10,972 KB |
testcase_89 | AC | 522 ms
10,988 KB |
testcase_90 | AC | 458 ms
10,660 KB |
testcase_91 | AC | 547 ms
10,904 KB |
testcase_92 | AC | 563 ms
10,940 KB |
testcase_93 | AC | 573 ms
10,640 KB |
ソースコード
#include <bits/stdc++.h> using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; using i128 = __int128_t; using u128 = __uint128_t; using isize = std::ptrdiff_t; using usize = std::size_t; class rep { struct Iter { usize itr; constexpr Iter(const usize pos) noexcept: itr(pos) { } constexpr void operator ++ () noexcept { ++itr; } constexpr bool operator != (const Iter& other) const noexcept { return itr != other.itr; } constexpr usize operator * () const noexcept { return itr; } }; const Iter first, last; public: explicit constexpr rep(const usize first, const usize last) noexcept: first(first), last(std::max(first, last)) { } constexpr Iter begin() const noexcept { return first; } constexpr Iter end() const noexcept { return last; } }; class revrep { struct Iter { usize itr; constexpr Iter(const usize pos) noexcept: itr(pos) { } constexpr void operator ++ () noexcept { --itr; } constexpr bool operator != (const Iter& other) const noexcept { return itr != other.itr; } constexpr usize operator * () const noexcept { return itr; } }; const Iter first, last; public: explicit constexpr revrep(const usize first, const usize last) noexcept: first(last - 1), last(std::min(first, last) - 1) { } constexpr Iter begin() const noexcept { return first; } constexpr Iter end() const noexcept { return last; } }; template <class T, T Div = 2> constexpr T INFTY = std::numeric_limits<T>::max() / Div; template <class T> using Vec = std::vector<T>; struct SemiRing { static constexpr SemiRing zero() { return SemiRing { -INFTY<i64> }; } static constexpr SemiRing one() { return SemiRing { INFTY<i64> }; } i64 x; constexpr SemiRing operator + (const SemiRing& other) const { return SemiRing { std::max(x, other.x) }; } constexpr SemiRing operator * (const SemiRing& other) const { return SemiRing { std::min(x, other.x) }; } }; void H_main() { // O(K^2 log N) ? // + ... max, x ... min の半環 // 中一でこんなの知ってるのか... // kitamasa法 書いたことないんだが // A[n+k] = B[0] * A[n] + B[1] * A[n+1] + ... + B[k-1] * A[n+k-1] usize K; u64 N; std::cin >> K >> N; Vec<SemiRing> A(K), B(K); for (auto& x: A) { std::cin >> x.x; } for (auto& x: B) { std::cin >> x.x; } const auto next = [&](const Vec<SemiRing>& vec) { Vec<SemiRing> ret(K, SemiRing::zero()); ret[0] = vec[K - 1] * B[0]; for (auto i: rep(0, K - 1)) { ret[i + 1] = vec[i] + vec[K - 1] * B[i + 1]; } return ret; }; const auto dbl = [&](const Vec<SemiRing>& vec) { Vec<Vec<SemiRing>> coeff(K, Vec<SemiRing>(K, SemiRing::zero())); coeff[0] = vec; for (auto i: rep(0, K - 1)) { coeff[i + 1] = next(coeff[i]); } Vec<SemiRing> ret(K, SemiRing::zero()); for (auto i: rep(0, K)) { for (auto j: rep(0, K)) { ret[i] = ret[i] + coeff[0][j] * coeff[j][i]; } } return ret; }; // C(K, *) = B // C(0, *) = { 1, 0, 0, ..., 0 } Vec<SemiRing> coeff(K, SemiRing::zero()); coeff[0] = SemiRing::one(); for (auto d: revrep(0, 64)) { coeff = dbl(coeff); if (N >> d & 1) { coeff = next(coeff); } } SemiRing ans = SemiRing::zero(); for (auto i: rep(0, K)) { ans = ans + A[i] * coeff[i]; } std::cout << ans.x << '\n'; return; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); H_main(); return 0; }