結果

問題 No.3367 Looks like a convolution
コンテスト
ユーザー cho435
提出日時 2025-10-29 16:29:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,172 bytes
コンパイル時間 3,012 ms
コンパイル使用メモリ 286,420 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-11-17 20:35:51
合計ジャッジ時間 8,910 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)

struct io_setup {
	io_setup() {
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout << fixed << setprecision(15);
	}
} io_setup;

namespace cho {

template <class S, auto op> struct sparse_table {
	static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
				  "op must work as S(S, S)");
	std::vector<std::vector<S>> st;
	int n;
	sparse_table() {};
	sparse_table(const std::vector<S>& dat) {
		n = dat.size();
		int lg = 1;
		while ((1 << lg) < n) lg++;
		st.resize(lg);
		st[0] = dat;
		for (int i = 0; i < lg - 1; i++) {
			int m = st[i].size() - (1 << i);
			st[i + 1].resize(m);
			for (int j = 0; j < m; j++) {
				st[i + 1][j] = op(st[i][j], st[i][j + (1 << i)]);
			}
		}
	}
	S prod(int l, int r) const {
		assert(0 <= l && l < r && r <= n);
		if (l + 1 == r) return st[0][l];
		int k = 31 - std::countl_zero((unsigned)(r - l - 1));
		return op(st[k][l], st[k][r - (1 << k)]);
	}
};

template <class S> S wrapper_max(const S& a, const S& b) {
	return std::max<S>(a, b);
}
template <class S>
using max_sparse_table = sparse_table<S, wrapper_max<S>>;
template <class S>
max_sparse_table<S> get_max_sparse_table(std::vector<S>& v) {
	return max_sparse_table<S>(v);
}

template <class S> S wrapper_min(const S& a, const S& b) {
	return std::min<S>(a, b);
}
template <class S>
using min_sparse_table = sparse_table<S, wrapper_min<S>>;
template <class S>
min_sparse_table<S> get_min_sparse_table(std::vector<S>& v) {
	return min_sparse_table<S>(v);
}

}  // namespace cho

vector<ll> greedy(vector<ll> a, vector<ll> b) {
	int n = a.size();
	assert((int)b.size() == n);
	auto ta = cho::get_min_sparse_table(a);
	auto tb = cho::get_min_sparse_table(b);
	vector<ll> res(n);
	rep(k, 0, n) {
		rep(i, 0, k + 1) {
			int j = k - i;
			res[k] += min(ta.prod(i, k + 1), tb.prod(j, k + 1));
		}
	}
	return res;
}

int main() {
	int n;
	cin >> n;
	vector<ll> a(n), b(n);
	rep(i, 0, n) cin >> a[i];
	rep(i, 0, n) cin >> b[i];
	auto c = greedy(a, b);
	rep(i, 0, n) cout << c[i] << ' ';
	cout << '\n';
}
0