結果
問題 | No.1247 ブロック登り |
ユーザー |
![]() |
提出日時 | 2020-10-03 20:18:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 503 ms / 3,000 ms |
コード長 | 3,035 bytes |
コンパイル時間 | 3,411 ms |
コンパイル使用メモリ | 381,796 KB |
最終ジャッジ日時 | 2025-01-15 02:14:31 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
// #pragma GCC optimize("Ofast")// #pragma GCC target("avx2,bmi,bmi2,lzcnt")// #define NDEBUG#include <bits/extc++.h>#include <x86intrin.h>struct rep {struct iter {int i;constexpr void operator++() { ++i; }constexpr int operator*() const { return i; }friend constexpr bool operator!=(iter a, iter b) { return *a != *b; }};const int l, r;constexpr rep(int _l, int _r) : l(std::min(_l, _r)), r(_r) {}constexpr rep(int n) : rep(0, n) {}constexpr iter begin() const { return {l}; }constexpr iter end() const { return {r}; }};struct per {struct iter {int i;constexpr void operator++() { --i; }constexpr int operator*() const { return i; }friend constexpr bool operator!=(iter a, iter b) { return *a != *b; }};const int l, r;constexpr per(int _l, int _r) : l(std::min(_l, _r)), r(_r) {}constexpr per(int n) : per(0, n) {}constexpr iter begin() const { return {r - 1}; }constexpr iter end() const { return {l - 1}; }};template <class T, class U>constexpr bool chmin(T& a, U&& b) {return b < a ? a = std::forward<U>(b), true : false;}template <class T, class U>constexpr bool chmax(T& a, U&& b) {return a < b ? a = std::forward<U>(b), true : false;}int main() {using namespace std;cin.tie(nullptr)->sync_with_stdio(false);constexpr int inf = 0x3f3f3f3f;int n, k;cin >> n >> k;vector<int> a(n);for (auto&& e : a) cin >> e;vector dp(k + 1, vector(n, vector(n, -inf)));for (int i : rep(n)) dp[k][i][i] = a[i] * k;for (int v : per(1, k + 1))for (int i : rep(n))for (int j : rep(n)) {if (dp[v][i][j] == -inf) continue;if (i < j) {if (i) {int nv = v - 1;chmax(dp[nv][i - 1][j], dp[v][i][j] + a[i - 1] * nv);}if (j + 1 < n) {int nv = v - abs((j + 1) - i);if (nv >= 0) chmax(dp[nv][j + 1][i], dp[v][i][j] + a[j + 1] * nv);}if (v >= 2) chmax(dp[v - 2][i][j], dp[v][i][j]);} else if (j < i) {if (i + 1 < n) {int nv = v - 1;chmax(dp[nv][i + 1][j], dp[v][i][j] + a[i + 1] * nv);}if (j) {int nv = v - abs((j - 1) - i);if (nv >= 0) chmax(dp[nv][j - 1][i], dp[v][i][j] + a[j - 1] * nv);}if (v >= 2) chmax(dp[v - 2][i][j], dp[v][i][j]);} else {assert(i == j);assert(v == k);if (i) chmax(dp[v - 1][i - 1][j], dp[v][i][j] + a[i - 1] * (v - 1));if (i + 1 < n)chmax(dp[v - 1][i + 1][j], dp[v][i][j] + a[i + 1] * (v - 1));}}vector ans(n, -inf);for (int v : rep(k + 1))for (int i : rep(n))for (int j : rep(n)) {if (i + v <= j) chmax(ans[i + v], dp[v][i][j]);if (i - v >= j) chmax(ans[i - v], dp[v][i][j]);}for (int e : ans) cout << e << '\n';}