結果

問題 No.1247 ブロック登り
ユーザー risujirohrisujiroh
提出日時 2020-10-03 07:03:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,047 bytes
コンパイル時間 3,709 ms
コンパイル使用メモリ 376,908 KB
実行使用メモリ 4,564 KB
最終ジャッジ日時 2023-09-25 04:47:21
合計ジャッジ時間 6,286 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 2 ms
4,376 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 3 ms
4,380 KB
testcase_23 AC 3 ms
4,376 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 112 ms
4,376 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #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);
  int n, k;
  cin >> n >> k;
  vector<int> c(n);
  for (auto&& e : c) cin >> e;
  if (k == 1) {
    for (int i : rep(n)) {
      int ans = -2e9;
      if (i) chmax(ans, c[i - 1]);
      if (i + 1 < n) chmax(ans, c[i + 1]);
      cout << ans << '\n';
    }
    exit(0);
  }

  auto can = [&](int i, int j, int h) -> bool {
    if ((abs(j - i) & 1) != (h & 1)) return false;
    if (abs(j - i) > h) return false;
    return true;
  };

  vector suff(2, vector<int>(n + 1));
  auto f = [&](int pos, int sz, int s, int d) -> int {
    return (s - d * pos) * (suff[0][pos] - suff[0][pos + sz]) +
           d * (suff[1][pos] - suff[1][pos + sz]);
  };

  auto go = [&] {
    for (int i : per(n)) {
      suff[0][i] = c[i] + suff[0][i + 1];
      suff[1][i] = c[i] * i + suff[1][i + 1];
    }
    vector mx(n, vector<int>(k + 1, -2e9));
    for (int a : rep(2, k + 1)) {
      for (int b : rep(1, k - 2 * a + 2)) {
        int sz = k - 2 * a + 2 - b;
        for (int l : rep(n - a - sz + 1)) {
          int cur = f(l, a, k - a + 1, 1) + f(l + a, sz, k - 2 * a + 1, -1);
          chmax(mx[l + a + sz - 1][b], cur);
        }
      }
      for (int l : rep(n - a + 1)) {
        int cur = f(l, a, k - a + 1, 1);
        chmax(mx[l][k - a + 1], cur);
      }
    }
    vector<int> res(n, -2e9);
    for (int i : rep(n))
      for (int j : rep(n))
        for (int h : rep(1, k + 1))
          if (can(i, j, h)) chmax(res[i], mx[j][h]);
    return res;
  };

  auto ans = go();
  reverse(begin(c), end(c));
  auto temp = go();
  for (int i : rep(n)) chmax(ans[i], temp[n - i - 1]);
  for (int e : ans) cout << e << '\n';
}
0