問題一覧 > 通常問題

No.3367 Looks like a convolution

レベル : / AI推定難易度 : 2225 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 16
作問者 : cho435 / テスター : jupiter_68 Naru820 noya2
お気に入りにしたユーザー ProblemId : 12798 / 自分の提出
問題文最終更新日: 2025-11-17 16:08:07
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 作問ハッカソンコンテスト 003 Day2 (順位表) の他の問題:

Problem Statement

You are given arrays $A=(A_0,A_1,\ldots,A_{N-1}) ,B=(B_0,B_1,\ldots,B_{N-1})$, each with $N$ elements. Output the array $C=(C_0,C_1,\ldots,C_{N-1})$ with $N$ elements, defined as follows. $$C_k = \sum_{i,j \geq 0 ,\ i+j = k} {\min( \min(A[i,k]), \min(B[j,k]) )}$$ Here, for an array $V$, $\min(V[a,b])$ denotes $\min(V_a,V_{a+1},\ldots,V_{b})$, and arrays are considered 0-indexed.

Constraints

  • All input values are integers.
  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq A_i \leq 10^9 \ (0 \leq i \leq N-1) $
  • $1 \leq B_i \leq 10^9 \ (0 \leq i \leq N-1) $

Input

$N$
$A_0 \  A_1 \ \ldots \ A_{N-1}$
$B_0 \  B_1 \ \ldots \ B_{N-1}$

Output

Output the elements of $C$ on a single line, separated by spaces.

Sample

Sample 1
Input
5
5 2 4 1 3
4 5 3 2 1
Output
4 4 7 4 5

For example, $C_2$ is $$ C_2 = \min(\min(A[0,2]), \min(B[2,2])) + \min(\min(A[1,2]), \min(B[1,2])) + \min(\min(A[2,2]), \min(B[0,2])) \\ = \min(\min(5,2,4),\min(3)) + \min(\min(2,4),\min(5,3)) + \min(\min(4),\min(4,5,3)) = 7 $$ .

Sample 2
Input
10
1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1
Output
1 11 111 1111 11111 21111 4111 611 81 10

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。