Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 166 点
問題文
高橋君は市役所で証明書を N 枚交付してもらいます。証明書は 1 枚につき A 円の手数料がかかります。
高橋君は B 円持っています。高橋君が N 枚すべての手数料を払えるなら Yes を、払えないなら No を出力してください。
制約
- 1 \leq N \leq 100
- 1 \leq A \leq 1000
- 1 \leq B \leq 100000
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A B
- 1 行目には、証明書の枚数 N 、 1 枚あたりの手数料 A 、高橋君の所持金 B がスペース区切りで与えられる。
出力
N 枚すべての手数料を払えるなら Yes を、払えないなら No を 1 行で出力せよ。
入力例 1
3 200 500
出力例 1
No
入力例 2
1 200 500
出力例 2
Yes
入力例 3
2 250 600
出力例 3
Yes
入力例 4
45 252 66831
出力例 4
Yes
入力例 5
63 662 32593
出力例 5
No
Score : 166 pts
Problem Statement
Takahashi will have N certificates issued at the city office. Each certificate costs A yen as a fee.
Takahashi has B yen. If he can pay the fees for all N certificates, print Yes; otherwise, print No.
Constraints
- 1 \leq N \leq 100
- 1 \leq A \leq 1000
- 1 \leq B \leq 100000
- All input values are integers.
Input
The input is given from standard input in the following format:
N A B
- The first line contains the number of certificates N, the fee per certificate A, and Takahashi's money B, separated by spaces.
Output
If he can pay the fees for all N certificates, print Yes; otherwise, print No, in a single line.
Sample Input 1
3 200 500
Sample Output 1
No
Sample Input 2
1 200 500
Sample Output 2
Yes
Sample Input 3
2 250 600
Sample Output 3
Yes
Sample Input 4
45 252 66831
Sample Output 4
Yes
Sample Input 5
63 662 32593
Sample Output 5
No
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 233 点
問題文
高橋君の家のフェンスには N 枚の板が一列に立っています。左端を 0 として、左から i 番目の板は位置 A_i にあります。板の位置は左から順に大きくなっており、 A_1 < A_2 < \cdots < A_N です。
隣り合う板の間の隙間は N - 1 か所あります。左から i 番目の板と i + 1 番目の板の間の隙間の幅は A_{i+1} - A_i です。
最も広い隙間は左から何番目の隙間かを求めてください。最も広い隙間が複数ある場合は、そのうち最も左のものを答えてください。
制約
- 2 \leq N \leq 100
- 0 \leq A_1 < A_2 < \cdots < A_N \leq 10000
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
- 1 行目には、板の枚数 N が与えられる。
- 2 行目には、各板の位置 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
出力
最も広い隙間が左から何番目かを 1 行で出力せよ。複数ある場合は最も左のものを出力せよ。
入力例 1
4 0 3 10 12
出力例 1
2
入力例 2
2 5 9
出力例 2
1
入力例 3
5 1 2 4 8 20
出力例 3
4
入力例 4
15 78 92 112 198 257 352 391 462 536 610 638 702 738 751 821
出力例 4
5
入力例 5
4 0 4 10 24
出力例 5
3
Score : 233 pts
Problem Statement
There are N boards standing in a row on the fence of Takahashi's house. Taking the left end as position 0, the i-th board from the left is at position A_i. The positions of the boards increase from left to right: A_1 < A_2 < \cdots < A_N.
There are N - 1 gaps between consecutive boards. The width of the gap between the i-th and (i+1)-th boards from the left is A_{i+1} - A_i.
Find the index (counted from the left) of the widest gap. If there are multiple widest gaps, answer the leftmost one.
Constraints
- 2 \leq N \leq 100
- 0 \leq A_1 < A_2 < \cdots < A_N \leq 10000
- All input values are integers.
Input
The input is given from standard input in the following format.
N A_1 A_2 \ldots A_N
- The first line contains the number of boards N.
- The second line contains the positions A_1, A_2, \ldots, A_N of the boards, separated by spaces.
Output
Print, in a single line, the index (counted from the left) of the widest gap. If there are multiple such gaps, print the leftmost one.
Sample Input 1
4 0 3 10 12
Sample Output 1
2
Sample Input 2
2 5 9
Sample Output 2
1
Sample Input 3
5 1 2 4 8 20
Sample Output 3
4
Sample Input 4
15 78 92 112 198 257 352 391 462 536 610 638 702 738 751 821
Sample Output 4
5
Sample Input 5
4 0 4 10 24
Sample Output 5
3
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君はスマートフォンのリズムゲームをプレイしています。このゲームでは、N 個のノーツが順番に流れてきます。
各ノーツ i（1 \leq i \leq N）には、基本スコア A_i が設定されています。
このゲームには「ボーナスタイム」という特殊なシステムがあります。高橋君は、ゲーム開始前に連続する K 個のノーツからなる区間をちょうど 1 つ選び、ボーナスタイムとして設定します。具体的には、ある整数 s（1 \leq s \leq N - K + 1）を選び、ノーツ s, s+1, \ldots, s+K-1 をボーナスタイムの対象とします。
ボーナスタイムの対象となったノーツから得られるスコアは基本スコアの 2 倍、それ以外のノーツから得られるスコアは基本スコアそのままです。最終的な得点は、すべてのノーツから得られるスコアの合計です。
s を選んだときの得点を式で表すと、
\sum_{\substack{i=1 \\ i \notin [s, s+K-1]}}^{N} A_i + \sum_{i=s}^{s+K-1} 2A_i = \sum_{i=1}^{N} A_i + \sum_{i=s}^{s+K-1} A_i
となります。すなわち、得点は全ノーツの基本スコアの合計に、ボーナスタイム対象区間の基本スコアの合計を加えたものです。
高橋君はハイスコアを狙っています。ボーナスタイムを設定する区間を最適に選んだとき、獲得できる得点の最大値を求めてください。
制約
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9（1 \leq i \leq N）
- 入力はすべて整数である
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、ノーツの数を表す整数 N と、ボーナスタイムを適用する連続区間の長さを表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各ノーツの基本スコアを表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
獲得できる得点の最大値を 1 行で出力せよ。
入力例 1
5 2 1 3 2 4 1
出力例 1
17
入力例 2
7 3 10 20 5 100 100 100 15
出力例 2
650
入力例 3
10 4 500000000 1 1 1 1 1 1 1 1 500000000
出力例 3
1500000011
Score : 333 pts
Problem Statement
Takahashi is playing a rhythm game on his smartphone. In this game, N notes appear in sequence.
Each note i (1 \leq i \leq N) has a base score A_i.
This game has a special system called "Bonus Time." Before the game starts, Takahashi must select exactly one interval consisting of K consecutive notes and set it as the Bonus Time. Specifically, he chooses an integer s (1 \leq s \leq N - K + 1) and designates notes s, s+1, \ldots, s+K-1 as the Bonus Time targets.
The score earned from notes within the Bonus Time is doubled (i.e., 2 times the base score), while the score earned from all other notes remains equal to their base score. The final score is the sum of the scores earned from all notes.
Expressing the score when s is chosen as a formula:
\sum_{\substack{i=1 \\ i \notin [s, s+K-1]}}^{N} A_i + \sum_{i=s}^{s+K-1} 2A_i = \sum_{i=1}^{N} A_i + \sum_{i=s}^{s+K-1} A_i
In other words, the score equals the sum of base scores of all notes plus the sum of base scores of the notes in the Bonus Time interval.
Takahashi is aiming for a high score. Find the maximum score he can achieve by optimally choosing the interval for the Bonus Time.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- All input values are integers.
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of notes and an integer K representing the length of the consecutive interval to which the Bonus Time is applied, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the base score of each note, separated by spaces.
Output
Print the maximum score that can be achieved in a single line.
Sample Input 1
5 2 1 3 2 4 1
Sample Output 1
17
Sample Input 2
7 3 10 20 5 100 100 100 15
Sample Output 2
650
Sample Input 3
10 4 500000000 1 1 1 1 1 1 1 1 500000000
Sample Output 3
1500000011
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君の住む街は、 H 行 W 列のマス目状の区画に分かれています。
上から i 行目、左から j 列目の区画を区画 (i, j) と呼びます。各区画 (i, j) には、通行料 A_{i, j} 円が定められています。
高橋君は最初、区画 (1, 1) にいます。高橋君は上下左右に隣接する区画への移動を繰り返して、区画 (H, W) へ到達したいと考えています。
具体的には、区画 (i, j) にいるとき、区画 (i-1, j), (i+1, j), (i, j-1), (i, j+1) のうち、街の内部にある（行番号が 1 以上 H 以下かつ列番号が 1 以上 W 以下である）区画のいずれかへ移動できます。街の外へ出るような移動はできません。
高橋君は、ある区画から区画 (r, c) へ移動するたびに、通行料として A_{r, c} 円を支払います。同じ区画を複数回訪れた場合も、移動して入るたびに通行料を支払います。
なお、移動を開始する前の時点で区画 (1, 1) にいることに対する通行料は支払いませんが、移動によって再び区画 (1, 1) へ入った場合は A_{1, 1} 円を支払います。
高橋君が区画 (1, 1) から移動を開始し、区画 (H, W) に到達して移動を終了するまでに支払う通行料の合計の最小値を求めてください。なお、目的地の区画 (H, W) に入る際に支払う通行料 A_{H, W} 円も合計に含みます。
制約
- 2 \leq H \leq 10^5
- 2 \leq W \leq 10^5
- H \times W \leq 2 \times 10^5
- 0 \leq A_{i, j} \leq 10^9 (1 \leq i \leq H, 1 \leq j \leq W)
- 入力はすべて整数
入力
入力は以下の形式で与えられる。
H W
A_{1, 1} A_{1, 2} \dots A_{1, W}
A_{2, 1} A_{2, 2} \dots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \dots A_{H, W}
出力
支払う通行料の合計の最小値を出力してください。
入力例 1
3 3 3 5 2 4 1 6 8 3 2
出力例 1
10
入力例 2
5 3 0 1 1 100 100 1 1 1 1 1 100 100 1 1 1
出力例 2
10
入力例 3
6 7 5 8 3 1 9 4 2 2 0 7 6 5 8 3 9 4 1 0 3 2 7 8 3 5 9 1 0 4 1 7 2 4 8 3 5 6 5 9 3 2 1 0
出力例 3
15
入力例 4
10 10 782194301 294810293 847102938 192840192 948102938 392019481 582019482 102948102 481029481 928401928 391029481 481029384 102948102 938401928 294810294 847102938 192840192 481029481 839201948 294810294 849102938 192840192 582019482 392019481 748291039 102948102 839201948 294810294 192840192 481029481 192840192 481029481 928401928 849102938 192840192 481029384 294810294 847102938 392019481 582019482 582019482 839201948 294810294 102948102 481029481 928401928 849102938 192840192 481029384 102948102 294810294 192840192 481029481 839201948 294810294 102948102 392019481 582019482 847102938 192840192 847102938 392019481 582019482 192840192 847102938 294810294 102948102 481029481 928401928 849102938 102948102 481029481 839201948 294810294 192840192 481029481 928401928 849102938 192840192 481029384 481029384 294810294 847102938 192840192 481029481 839201948 294810294 102948102 392019481 582019482 928401928 849102938 192840192 481029384 102948102 392019481 582019482 847102938 192840192 294810294
出力例 4
6169046258
入力例 5
2 2 1000000000 1000000000 1000000000 1000000000
出力例 5
2000000000
Score : 400 pts
Problem Statement
The city where Takahashi lives is divided into a grid of blocks with H rows and W columns.
Let (i, j) denote the block at the i-th row from the top and j-th column from the left. Each block (i, j) has a designated toll of A_{i, j} yen.
Initially, Takahashi is at block (1, 1). He wants to reach block (H, W) by repeatedly moving to vertically or horizontally adjacent blocks.
Specifically, when he is at block (i, j), he can move to one of the blocks (i-1, j), (i+1, j), (i, j-1), and (i, j+1) that lies inside the city (that is, its row number is between 1 and H, inclusive, and its column number is between 1 and W, inclusive). He cannot move outside the city.
Each time Takahashi moves from some block to block (r, c), he pays a toll of A_{r, c} yen. Even if he visits the same block multiple times, he pays the toll every time he enters it.
Note that he does not pay a toll for being at block (1, 1) before starting his movement, but if he re-enters block (1, 1) by a move, he pays A_{1, 1} yen.
Find the minimum total toll Takahashi must pay from starting his movement at block (1, 1) until reaching block (H, W) and finishing his movement. Note that the toll of A_{H, W} yen paid upon entering the destination block (H, W) is included in the total.
Constraints
- 2 \leq H \leq 10^5
- 2 \leq W \leq 10^5
- H \times W \leq 2 \times 10^5
- 0 \leq A_{i, j} \leq 10^9 (1 \leq i \leq H, 1 \leq j \leq W)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
H W
A_{1, 1} A_{1, 2} \dots A_{1, W}
A_{2, 1} A_{2, 2} \dots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \dots A_{H, W}
Output
Print the minimum total toll to be paid.
Sample Input 1
3 3 3 5 2 4 1 6 8 3 2
Sample Output 1
10
Sample Input 2
5 3 0 1 1 100 100 1 1 1 1 1 100 100 1 1 1
Sample Output 2
10
Sample Input 3
6 7 5 8 3 1 9 4 2 2 0 7 6 5 8 3 9 4 1 0 3 2 7 8 3 5 9 1 0 4 1 7 2 4 8 3 5 6 5 9 3 2 1 0
Sample Output 3
15
Sample Input 4
10 10 782194301 294810293 847102938 192840192 948102938 392019481 582019482 102948102 481029481 928401928 391029481 481029384 102948102 938401928 294810294 847102938 192840192 481029481 839201948 294810294 849102938 192840192 582019482 392019481 748291039 102948102 839201948 294810294 192840192 481029481 192840192 481029481 928401928 849102938 192840192 481029384 294810294 847102938 392019481 582019482 582019482 839201948 294810294 102948102 481029481 928401928 849102938 192840192 481029384 102948102 294810294 192840192 481029481 839201948 294810294 102948102 392019481 582019482 847102938 192840192 847102938 392019481 582019482 192840192 847102938 294810294 102948102 481029481 928401928 849102938 102948102 481029481 839201948 294810294 192840192 481029481 928401928 849102938 192840192 481029384 481029384 294810294 847102938 192840192 481029481 839201948 294810294 102948102 392019481 582019482 928401928 849102938 192840192 481029384 102948102 392019481 582019482 847102938 192840192 294810294
Sample Output 4
6169046258
Sample Input 5
2 2 1000000000 1000000000 1000000000 1000000000
Sample Output 5
2000000000
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
高橋君は文化祭の実行委員長を務めています。文化祭では N 個の展示ブースが横一列に並んで設置されます。左から順にブース 1 , ブース 2 , ..., ブース N と番号が付けられています。
N 個の出展団体がそれぞれ 1 つずつブースを使用します。各出展団体 i には、展示の派手さを表す値 C_i が定まっています。隣り合うブースに配置された 2 つの出展団体の派手さの差の絶対値が「コントラスト」として計算されます。すなわち、ブース j に出展団体 p が、ブース j+1 に出展団体 q が配置されているとき、その隣り合うペアのコントラストは |C_p - C_q| です。
文化祭全体の「総コントラスト」は、隣り合う全てのペア（ N - 1 組）のコントラストの合計です。
高橋君は、来場者が歩きながら変化に富んだ展示を楽しめるよう、総コントラストをできるだけ大きくしたいと考えています。高橋君は N 個の出展団体のブースへの配置を自由に決めることができます。
総コントラストを最大化するとき、その最大値を求めてください。
制約
- 2 \leq N \leq 10^6
- 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数である。
入力
N C_1 C_2 \ldots C_N
- 1 行目には、出展団体の数を表す整数 N が与えられる。
- 2 行目には、各出展団体の派手さを表す N 個の整数 C_1, C_2, \ldots, C_N がスペース区切りで与えられる。
出力
総コントラストの最大値を 1 行で出力せよ。
入力例 1
4 1 3 8 10
出力例 1
23
入力例 2
5 5 5 5 5 5
出力例 2
0
入力例 3
12 4 15 15 8 23 42 16 9 31 7 7 50
出力例 3
254
入力例 4
30 1000000000 1 500000000 250000000 750000000 123456789 987654321 333333333 666666666 42 999999999 314159265 271828182 161803398 141421356 173205080 223606797 707106781 888888888 111111111 222222222 444444444 555555555 777777777 99999999 900000000 800000000 700000000 600000000 400000000
出力例 4
16859449268
入力例 5
2 1 1000000000
出力例 5
999999999
Score : 433 pts
Problem Statement
Takahashi is the chairperson of the school festival committee. At the festival, N exhibition booths will be set up in a horizontal row. The booths are numbered 1, 2, \ldots, N from left to right.
There are N exhibiting groups, and each group will use exactly one booth. Each group i has a value C_i representing the "flashiness" of its exhibition. The absolute difference in flashiness between two groups placed in adjacent booths is defined as the "contrast". Specifically, if group p is placed in booth j and group q is placed in booth j+1, the contrast of this adjacent pair is |C_p - C_q|.
The "total contrast" of the entire festival is the sum of the contrasts of all adjacent pairs (N - 1 pairs).
Takahashi wants to maximize the total contrast so that visitors can enjoy a highly varied sequence of exhibitions as they walk. He can freely decide the assignment of the N groups to the booths.
Find the maximum possible total contrast.
Constraints
- 2 \leq N \leq 10^6
- 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
- All input values are integers.
Input
N C_1 C_2 \ldots C_N
- The first line contains an integer N, representing the number of exhibiting groups.
- The second line contains N space-separated integers C_1, C_2, \ldots, C_N, representing the flashiness of each group.
Output
Print the maximum possible total contrast in a single line.
Sample Input 1
4 1 3 8 10
Sample Output 1
23
Sample Input 2
5 5 5 5 5 5
Sample Output 2
0
Sample Input 3
12 4 15 15 8 23 42 16 9 31 7 7 50
Sample Output 3
254
Sample Input 4
30 1000000000 1 500000000 250000000 750000000 123456789 987654321 333333333 666666666 42 999999999 314159265 271828182 161803398 141421356 173205080 223606797 707106781 888888888 111111111 222222222 444444444 555555555 777777777 99999999 900000000 800000000 700000000 600000000 400000000
Sample Output 4
16859449268
Sample Input 5
2 1 1000000000
Sample Output 5
999999999