#include <iostream> #include <algorithm> #include <vector> //#include <bitset> #include <climits> using tab = std::vector<long long>; //using uint64_t = uint_least64_t; inline uint64_t get_n_bits(uint64_t i) { i = i - ((i >> 1) & 0x5555555555555555); i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333); return (((i + (i >> 4)) & 0xF0F0F0F0F0F0F0F) * 0x101010101010101) >> 56; } inline long long get_a(const uint64_t n, const uint64_t m, const tab& as) { tab sums(n + 1, LLONG_MIN); sums[0] = 0ul; for (uint64_t t = m;; --t) { const uint64_t beg = std::min(n, m - t + 1); const uint64_t end = n < t + 1 ? 0ull : n - t - 1; const long long n_bits = get_n_bits(t); for (uint64_t i = beg; i > end; --i) { const long long new_sum = sums[i - 1] + n_bits * as[n - i]; if (new_sum > sums[i]) sums[i] = new_sum; } if (t == 0) break; } return sums.back(); } int main() { uint64_t n, m; std::cin >> n >> m; tab as(n); for (int i = 0; i < n; ++i) std::cin >> as[i]; std::cout << get_a(n, m, as); }
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 | #include <iostream> #include <algorithm> #include <vector> //#include <bitset> #include <climits> using tab = std::vector<long long>; //using uint64_t = uint_least64_t; inline uint64_t get_n_bits(uint64_t i) { i = i - ((i >> 1) & 0x5555555555555555); i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333); return (((i + (i >> 4)) & 0xF0F0F0F0F0F0F0F) * 0x101010101010101) >> 56; } inline long long get_a(const uint64_t n, const uint64_t m, const tab& as) { tab sums(n + 1, LLONG_MIN); sums[0] = 0ul; for (uint64_t t = m;; --t) { const uint64_t beg = std::min(n, m - t + 1); const uint64_t end = n < t + 1 ? 0ull : n - t - 1; const long long n_bits = get_n_bits(t); for (uint64_t i = beg; i > end; --i) { const long long new_sum = sums[i - 1] + n_bits * as[n - i]; if (new_sum > sums[i]) sums[i] = new_sum; } if (t == 0) break; } return sums.back(); } int main() { uint64_t n, m; std::cin >> n >> m; tab as(n); for (int i = 0; i < n; ++i) std::cin >> as[i]; std::cout << get_a(n, m, as); } |