Skyscrapers

codeforces.com

問題概要

簡単に言えば

  1. ある配列が与えられる
  2. ある要素1つを選ぶ
  3. その要素より左は広義単調増加、右は広義単調増加ように配列の各要素の値を減らす
  4. 操作後の配列のうち総和が最大となるときの配列を出力せよ。

解法

ある要素を実際に選んでみて操作後の配列を構築して総和を出すやりかたで通した。計算量はO(n2)で、制約がn <= 1000なので通る。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define in(v) v; cin >> v;
#define all(f,c,...) (([&](decltype((c)) cccc) { return (f)(begin(cccc), end(cccc), ## __VA_ARGS__); })(c))
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,n) for(int i=(n);i>=0;--i)

template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}

int main() {
  int in(N);
  vector<int> A(N);
  rep(i, N) cin >> A[i];

  long long ans = 0;
  int max_i = 0;
  rep(i, N) {
    // A[i]を頂上としたときについて見ていく
    long long sum = A[i];
    int max_A = A[i];
    rep(j, i+1, N) {
      // 右側が単調減少となるようにする
      chmin(max_A, A[j]);
      sum += max_A;
    }
    max_A = A[i];
    rrep(j, i-1) {
      // 左側も右側と同様
      chmin(max_A, A[j]);
      sum += max_A;
    }
    if (ans <= sum) {
      ans = sum;
      max_i = i;
    }
  }

  rrep(i, max_i-1) chmin(A[i], A[i+1]);
  rep(i, max_i, N-1) chmin(A[i+1], A[i]);
  rep(i, N) {
    if (i) cout << " ";
    cout << A[i];
  }
  cout << endl;

  return 0;
}