結果

問題 No.1247 ブロック登り
ユーザー risujiroh
提出日時 2020-10-03 07:03:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,047 bytes
コンパイル時間 3,779 ms
コンパイル使用メモリ 379,924 KB
最終ジャッジ日時 2025-01-15 01:53:39
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 19
権限があれば一括ダウンロードができます

ソースコード

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