AtCoder Daily Training ALL 2026/04/14 18:00start

A - 9x9

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

1 文字目が数字、2 文字目が文字 x、3 文字目が数字であるような 3 文字の文字列 S が与えられます。

S の 2 つの数の積を求めてください。

制約

S は 1 文字目が 1 以上 9 以下の整数、2 文字目が文字 x、3 文字目が 1 以上 9 以下の整数であるような 3 文字の文字列

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを整数として出力せよ。

入力例 1

3x8

出力例 1

3 \times 8 = 24 より、24 を出力します。

入力例 2

9x9

出力例 2

9 \times 9 = 81 より、81 を出力します。

Score : 100 points

Problem Statement

You are given a 3-character string S, where the first character is a digit, the second character is the character x, and the third character is a digit.

Find the product of the two numbers in S.

Constraints

S is a 3-character string where the first character is an integer between 1 and 9, inclusive, the second character is the character x, and the third character is an integer between 1 and 9, inclusive.

Input

The input is given from Standard Input in the following format:

Output

Print the answer as an integer.

Sample Input 1

3x8

Sample Output 1

From 3 \times 8 = 24, print 24.

Sample Input 2

9x9

Sample Output 2

From 9 \times 9 = 81, print 81.

B - Triple Four

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

A の中に同じ要素が 3 つ以上連続する箇所が存在するか判定してください。

より厳密には、 1 以上 N-2 以下の整数 i であって A_i=A_{i+1}=A_{i+2} を満たすものが存在するか判定してください。

制約

3\le N\le 100
1\le A_i\le 100
入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \ldots A_N

出力

A の中に同じ要素が 3 つ以上連続する箇所が存在するならば Yes を、存在しないならば No を出力せよ。

入力例 1

5
1 4 4 4 2

出力例 1

Yes

A=(1,4,4,4,2) です。 4 が 3 つ連続している箇所が存在するので、 Yes を出力してください。

入力例 2

6
2 4 4 2 2 4

出力例 2

No

A=(2,4,4,2,2,4) です。同じ要素が 3 つ以上連続している箇所は存在しないので、 No を出力してください。

入力例 3

8
1 4 2 5 7 7 7 2

出力例 3

Yes

入力例 4

10
1 2 3 4 5 6 7 8 9 10

出力例 4

No

入力例 5

13
1 1 1 1 1 1 1 1 1 1 1 1 1

出力例 5

Yes

Score : 100 points

Problem Statement

You are given an integer sequence of length N: A = (A_1,A_2,\ldots,A_N).

Determine whether there is a place in A where the same element appears three or more times in a row.

More formally, determine whether there exists an integer i with 1 \le i \le N-2 such that A_i = A_{i+1} = A_{i+2}.

Constraints

3 \le N \le 100
1 \le A_i \le 100
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

Output

If there is a place in A where the same element appears three or more times in a row, print Yes. Otherwise, print No.

Sample Input 1

5
1 4 4 4 2

Sample Output 1

Yes

We have A=(1,4,4,4,2). There is a place where 4 appears three times in a row, so print Yes.

Sample Input 2

6
2 4 4 2 2 4

Sample Output 2

No

We have A=(2,4,4,2,2,4). There is no place where the same element appears three or more times in a row, so print No.

Sample Input 3

8
1 4 2 5 7 7 7 2

Sample Output 3

Yes

Sample Input 4

10
1 2 3 4 5 6 7 8 9 10

Sample Output 4

No

Sample Input 5

13
1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 5

Yes

C - Line Sensor

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と表します。
各マスの状態は文字 C_{i,j} で表されます。C_{i,j} が . ならば (i, j) には何も置かれておらず、 # ならば箱が 1 個置かれています。

1 \leq j \leq W を満たす整数 j に対して、整数 X_j を次のように定義します。

j 列目に置かれている箱の個数。言い換えると、C_{i,j} が # であるような整数 i の個数。

X_1, X_2, \dots, X_W をすべて求めてください。

制約

1 \leq H \leq 1000
1 \leq W \leq 1000
H, W は整数
C_{i, j} は . または #

入力

入力は以下の形式で標準入力から与えられる。

H W
C_{1,1}C_{1,2}\dots C_{1,W}
C_{2,1}C_{2,2}\dots C_{2,W}
\vdots
C_{H,1}C_{H,2}\dots C_{H,W}

出力

X_1, X_2, \dots, X_W を以下の形式に従って出力せよ。

X_1 X_2 \dots X_W

入力例 1

3 4
#..#
.#.#
.#.#

出力例 1

1 2 0 3

1 列目の箱が置かれているマスは (1, 1) の 1 ヵ所です。よって X_1 = 1 です。
2 列目の箱が置かれているマスは (2, 2), (3, 2) の 2 ヵ所です。よって X_2 = 2 です。
3 列目の箱が置かれているマスは存在しません。よって X_3 = 0 です。
4 列目の箱が置かれているマスは (1, 4), (2, 4), (3, 4) の 3 ヵ所です。よって X_4 = 3 です。
よって (X_1, X_2, X_3, X_4) = (1, 2, 0, 3) が答えとなります。

入力例 2

3 7
.......
.......
.......

出力例 2

0 0 0 0 0 0 0

箱が置かれているマスが存在しない場合もあります。

入力例 3

8 3
.#.
###
.#.
.#.
.##
..#
##.
.##

出力例 3

2 7 4

入力例 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

出力例 4

0 5 1 2 2 0 0 5 3 3 3 3 0 0 1 1 3 1 1 0 0 5 3 3 3 3 0 0 5 1 1 1 5 0 0 3 2 2 2 2 0 0 5 3 3 3 3

Score : 200 points

Problem Statement

There is a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
The squares are described by characters C_{i,j}. If C_{i,j} is ., (i, j) is empty; if it is #, (i, j) contains a box.

For integers j satisfying 1 \leq j \leq W, let the integer X_j defined as follows.

X_j is the number of boxes in the j-th column. In other words, X_j is the number of integers i such that C_{i,j} is #.

Find all of X_1, X_2, \dots, X_W.

Constraints

1 \leq H \leq 1000
1 \leq W \leq 1000
H and W are integers.
C_{i, j} is . or #.

Input

The input is given from Standard Input in the following format:

H W
C_{1,1}C_{1,2}\dots C_{1,W}
C_{2,1}C_{2,2}\dots C_{2,W}
\vdots
C_{H,1}C_{H,2}\dots C_{H,W}

Output

Print X_1, X_2, \dots, X_W in the following format:

X_1 X_2 \dots X_W

Sample Input 1

3 4
#..#
.#.#
.#.#

Sample Output 1

1 2 0 3

In the 1-st column, one square, (1, 1), contains a box. Thus, X_1 = 1.
In the 2-nd column, two squares, (2, 2) and (3, 2), contain a box. Thus, X_2 = 2.
In the 3-rd column, no squares contain a box. Thus, X_3 = 0.
In the 4-th column, three squares, (1, 4), (2, 4), and (3, 4), contain a box. Thus, X_4 = 3.
Therefore, the answer is (X_1, X_2, X_3, X_4) = (1, 2, 0, 3).

Sample Input 2

3 7
.......
.......
.......

Sample Output 2

0 0 0 0 0 0 0

There may be no square that contains a box.

Sample Input 3

8 3
.#.
###
.#.
.#.
.##
..#
##.
.##

Sample Output 3

2 7 4

Sample Input 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

Sample Output 4

0 5 1 2 2 0 0 5 3 3 3 3 0 0 1 1 3 1 1 0 0 5 3 3 3 3 0 0 5 1 1 1 5 0 0 3 2 2 2 2 0 0 5 3 3 3 3

D - Music Player

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は音楽プレイヤーを持っています。はじめ、音量は 0 であり、曲は停止中です。

これから、Q 回の操作を順に行います。i 回目の操作は整数 A_i によって表され、操作の内容は以下の通りです。

A_i = 1 のとき、音量を 1 上げる。
A_i = 2 のとき、現在の音量が 1 以上であれば音量を 1 下げ、0 であれば何もしない。
A_i = 3 のとき、曲が停止中であれば曲を再生し、曲が再生中であれば曲を停止する。

i = 1, 2, \ldots, Q に対して、以下の問題を解いてください。

i 回目の操作を終えた直後に音量 3 以上で音楽が再生されているか判定せよ。

制約

1 \leq Q \leq 2 \times 10^5
A_i \in \lbrace 1, 2, 3 \rbrace
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

Q
A_1
A_2
\vdots
A_Q

出力

Q 行出力せよ。i 行目には、i 回目の操作を終えた直後に音量 3 以上で音楽が再生されているならば Yes を、そうでないならば No を出力せよ。

入力例 1

出力例 1

No
No
No
No
No
No
No
Yes
Yes
No

1 回目の操作を終えた後、音量は 0 で曲は停止中です。
2 回目の操作を終えた後、音量は 1 で曲は停止中です。
3 回目の操作を終えた後、音量は 1 で曲は再生中です。
4 回目の操作を終えた後、音量は 2 で曲は再生中です。
5 回目の操作を終えた後、音量は 2 で曲は停止中です。
6 回目の操作を終えた後、音量は 3 で曲は停止中です。
7 回目の操作を終えた後、音量は 4 で曲は停止中です。
8 回目の操作を終えた後、音量は 4 で曲は再生中です。
9 回目の操作を終えた後、音量は 3 で曲は再生中です。
10 回目の操作を終えた後、音量は 2 で曲は再生中です。

Score : 200 points

Problem Statement

Takahashi has a music player. Initially, the volume is 0 and the music is stopped.

From now on, Q operations will be performed in order. The i-th operation is represented by an integer A_i, which means the following:

If A_i = 1, increase the volume by 1.
If A_i = 2, if the current volume is 1 or more, decrease it by 1; if it is 0, do nothing.
If A_i = 3, if the music is stopped, play it; if the music is playing, stop it.

For i = 1, 2, \ldots, Q, solve the following problem:

Determine whether the music is playing at volume 3 or more immediately after the i-th operation.

Constraints

1 \leq Q \leq 2 \times 10^5
A_i \in \lbrace 1, 2, 3 \rbrace
All input values are integers.

Input

The input is given from Standard Input in the following format:

Q
A_1
A_2
\vdots
A_Q

Output

Output Q lines. The i-th line should contain Yes if the music is playing at volume 3 or more immediately after the i-th operation, and No otherwise.

Sample Input 1

Sample Output 1

No
No
No
No
No
No
No
Yes
Yes
No

After the 1-st operation, the volume is 0 and the music is stopped.
After the 2-nd operation, the volume is 1 and the music is stopped.
After the 3-rd operation, the volume is 1 and the music is playing.
After the 4-th operation, the volume is 2 and the music is playing.
After the 5-th operation, the volume is 2 and the music is stopped.
After the 6-th operation, the volume is 3 and the music is stopped.
After the 7-th operation, the volume is 4 and the music is stopped.
After the 8-th operation, the volume is 4 and the music is playing.
After the 9-th operation, the volume is 3 and the music is playing.
After the 10-th operation, the volume is 2 and the music is playing.

E - Snuke the Cookie Picker

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

縦 H マス, 横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i, j) と呼びます。
はじめ、グリッド上には、ある 縦横 2 マス以上 の部分長方形の内部にあるマスにクッキーが 1 枚ずつ置かれていて、それ以外のマスにはクッキーが置かれていません。
形式的に説明すると、以下の条件を全て満たす 4 つの整数の組 (a,b,c,d) がただ 1 つ存在します。

1 \leq a \lt b \leq H
1 \leq c \lt d \leq W
グリッド上のマスのうち、a \leq i \leq b, c \leq j \leq d を満たす全てのマス (i, j) にはクッキーが 1 枚ずつ置かれていて、それ以外のマスにはクッキーが置かれていない。

ところが、すぬけ君がグリッド上のクッキーのどれか 1 枚を取って食べてしまいました。
すぬけ君がクッキーを取ったマスは、クッキーが置かれていない状態に変わります。

すぬけ君がクッキーを食べた後のグリッドの状態が入力として与えられます。
マス (i, j) の状態は文字 S_{i,j} として与えられて、# はクッキーが置かれているマスを, . はクッキーが置かれていないマスを意味します。
すぬけ君が食べたクッキーが元々置かれていたマスを答えてください。(答えは一意に定まります。)

制約

2 \leq H, W \leq 500
S_{i,j} は # または .

入力

入力は以下の形式で標準入力から与えられる。

H W
S_{1,1}S_{1,2}\dotsS_{1,W}
S_{2,1}S_{2,2}\dotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\dotsS_{H,W}

出力

すぬけ君が食べたクッキーが元々置かれていたマスを (i, j) とする。i, j をこの順に空白区切りで出力せよ。

入力例 1

5 6
......
..#.#.
..###.
..###.
......

出力例 1

2 4

はじめ、クッキーは (2, 3) を左上、(4, 5) を右下とする部分長方形の内部にあるマスに置かれていて、すぬけ君は (2, 4) にあるクッキーを食べたことがわかります。よって (2, 4) を出力します。

入力例 2

3 2
#.
##
##

出力例 2

1 2

はじめ、クッキーは (1, 1) を左上、(3, 2) を右下とする部分長方形の内部にあるマスに置かれていて、すぬけ君は (1, 2) にあるクッキーを食べたことがわかります。

入力例 3

6 6
..####
..##.#
..####
..####
..####
......

出力例 3

2 5

Score : 300 points

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top and the j-th column from the left.
Initially, there was one cookie on each square inside a rectangle whose height and width were at least 2 squares long, and no cookie on the other squares.
Formally, there was exactly one quadruple of integers (a,b,c,d) that satisfied all of the following conditions.

1 \leq a \lt b \leq H
1 \leq c \lt d \leq W
There was one cookie on each square (i, j) such that a \leq i \leq b, c \leq j \leq d, and no cookie on the other squares.

However, Snuke took and ate one of the cookies on the grid.
The square that contained that cookie is now empty.

As the input, you are given the state of the grid after Snuke ate the cookie.
The state of the square (i, j) is given as the character S_{i,j}, where # means a square with a cookie, and . means a square without one.
Find the square that contained the cookie eaten by Snuke. (The answer is uniquely determined.)

Constraints

2 \leq H, W \leq 500
S_{i,j} is # or ..

Input

The input is given from Standard Input in the following format:

H W
S_{1,1}S_{1,2}\dotsS_{1,W}
S_{2,1}S_{2,2}\dotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\dotsS_{H,W}

Output

Let (i, j) the square contained the cookie eaten by Snuke. Print i and j in this order, separated by a space.

Sample Input 1

5 6
......
..#.#.
..###.
..###.
......

Sample Output 1

2 4

Initially, cookies were on the squares inside the rectangle with (2, 3) as the top-left corner and (4, 5) as the bottom-right corner, and Snuke ate the cookie on (2, 4). Thus, you should print (2, 4).

Sample Input 2

3 2
#.
##
##

Sample Output 2

1 2

Initially, cookies were placed on the squares inside the rectangle with (1, 1) as the top-left corner and (3, 2) as the bottom-right corner, and Snuke ate the cookie at (1, 2).

Sample Input 3

6 6
..####
..##.#
..####
..####
..####
......

Sample Output 3

2 5

F - AtCoder Magics

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

高橋くんは、カードゲーム「AtCoder Magics」のカードを N 枚持っています。i 番目のカードをカード i と呼ぶことにします。各カードには強さとコストのパラメーターがあり、カード i の強さは A_i で、コストは C_i です。

高橋くんは、弱いカードは要らないので捨てることにしました。具体的には、以下の操作をできなくなるまで繰り返します。

2 つのカード x, y であって、 A_x > A_y かつ C_x < C_y であるようなものを選ぶ。カード y を捨てる。

操作ができなくなったとき、捨てられなかったカードの集合は一意に定まることが証明できます。これを求めてください。

制約

2 \leq N \leq 2 \times 10^5
1 \leq A_i, C_i \leq 10^9
A_1, A_2, \dots ,A_N は全て異なる
C_1, C_2, \dots ,C_N は全て異なる
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 C_1
A_2 C_2
\vdots
A_N C_N

出力

捨てられなかったカードは m 枚あり、それらの番号が昇順に i_1, i_2, \dots ,i_m であったとする。このとき、以下の形式で出力せよ。

m
i_1 i_2 \cdots i_m

入力例 1

出力例 1

2
2 3

カード 1, 3 に注目すると、 A_1 < A_3 かつ C_1 > C_3 なのでカード 1 を捨てることができます。

それ以上操作をすることはできません。このときカード 2, 3 が残っているので、これらを出力します。

入力例 2

出力例 2

5
1 2 3 4 5

この場合、どのカードも捨てることができません。

入力例 3

出力例 3

4
2 3 5 6

Score : 350 points

Problem Statement

Takahashi has N cards from the card game "AtCoder Magics." The i-th card will be called card i. Each card has two parameters: strength and cost. Card i has a strength of A_i and a cost of C_i.

He does not like weak cards, so he will discard them. Specifically, he will repeat the following operation until it can no longer be performed:

Choose two cards x and y such that A_x > A_y and C_x < C_y. Discard card y.

It can be proved that the set of remaining cards when the operations can no longer be performed is uniquely determined. Find this set of cards.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq A_i, C_i \leq 10^9
A_1, A_2, \dots ,A_N are all distinct.
C_1, C_2, \dots ,C_N are all distinct.
All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 C_1
A_2 C_2
\vdots
A_N C_N

Output

Let there be m remaining cards, cards i_1, i_2, \dots, i_m, in ascending order. Print these in the following format:

m
i_1 i_2 \cdots i_m

Sample Input 1

Sample Output 1

2
2 3

Focusing on cards 1 and 3, we have A_1 < A_3 and C_1 > C_3, so card 1 can be discarded.

No further operations can be performed. At this point, cards 2 and 3 remain, so print them.

Sample Input 2

Sample Output 2

5
1 2 3 4 5

In this case, no cards can be discarded.

Sample Input 3

Sample Output 3

4
2 3 5 6

G - Stones

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

数列 (A_1,\ldots,A_K) を使って、高橋君と青木君が石取りゲームをします。

最初、山には N 個の石があります。高橋君から順に、二人が交互に次の操作を行います。

現在山にある石の個数以下であるような A_i を 1 つ選ぶ。山から A_i 個の石を取り除く。

山から石がなくなったとき、ゲームは終了します。

二人がともに、ゲーム終了までに自分が取り除いた石の個数を最大化しようとするとき、高橋君は何個の石を取り除くことができますか？

制約

1 \leq N \leq 10^4
1 \leq K \leq 100
1 = A_1 < A_2 < \ldots < A_K \leq N
入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2 \ldots A_K

出力

答えを出力せよ。

入力例 1

10 2
1 4

出力例 1

ゲームの進行の一例は以下の通りです。

高橋君が山から 4 個の石を取り除く。
青木君が山から 4 個の石を取り除く。
高橋君が山から 1 個の石を取り除く。
青木君が山から 1 個の石を取り除く。

この例では高橋君は 5 個の石を取り除くことができます。高橋君が 6 個以上の石を取り除くことはできないためこれが最大です。

高橋君は 5 個の石を取り除くことができるゲームの進行の例には、他にも次のようなものがあります。

高橋君が山から 1 個の石を取り除く。
青木君が山から 4 個の石を取り除く。
高橋君が山から 4 個の石を取り除く。
青木君が山から 1 個の石を取り除く。

入力例 2

11 4
1 2 3 6

出力例 2

ゲームの進行の一例は以下の通りです。

高橋君が山から 6 個の石を取り除く。
青木君が山から 3 個の石を取り除く。
高橋君が山から 2 個の石を取り除く。

この例では高橋君は 8 個の石を取り除くことができます。高橋君が 9 個以上の石を取り除くことはできないためこれが最大です。

入力例 3

10000 10
1 2 4 8 16 32 64 128 256 512

出力例 3

Score : 400 points

Problem Statement

Takahashi and Aoki will play a game of taking stones using a sequence (A_1, \ldots, A_K).

There is a pile that initially contains N stones. The two players will alternately perform the following operation, with Takahashi going first.

Choose an A_i that is at most the current number of stones in the pile. Remove A_i stones from the pile.

The game ends when the pile has no stones.

If both players attempt to maximize the total number of stones they remove before the end of the game, how many stones will Takahashi remove?

Constraints

1 \leq N \leq 10^4
1 \leq K \leq 100
1 = A_1 < A_2 < \ldots < A_K \leq N
All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_K

Output

Print the answer.

Sample Input 1

10 2
1 4

Sample Output 1

Below is one possible progression of the game.

Takahashi removes 4 stones from the pile.
Aoki removes 4 stones from the pile.
Takahashi removes 1 stone from the pile.
Aoki removes 1 stone from the pile.

In this case, Takahashi removes 5 stones. There is no way for him to remove 6 or more stones, so this is the maximum.

Below is another possible progression of the game where Takahashi removes 5 stones.

Takahashi removes 1 stone from the pile.
Aoki removes 4 stones from the pile.
Takahashi removes 4 stones from the pile.
Aoki removes 1 stone from the pile.

Sample Input 2

11 4
1 2 3 6

Sample Output 2

Below is one possible progression of the game.

Takahashi removes 6 stones.
Aoki removes 3 stones.
Takahashi removes 2 stones.

In this case, Takahashi removes 8 stones. There is no way for him to remove 9 or more stones, so this is the maximum.

Sample Input 3

10000 10
1 2 4 8 16 32 64 128 256 512

Sample Output 3

H - Destruction

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 頂点 M 辺の連結無向グラフがあります。
頂点には 1 から N の番号が、辺には 1 から M の番号がついており、辺 i は頂点 A_i と B_i を結んでいます。

高橋君は、このグラフから 0 個以上の辺を取り除こうとしています。

辺 i を取り除くと、C_i \geq 0 のとき C_i の報酬を得、C_i<0 のとき |C_i| の罰金を払います。

辺を取り除いたあともグラフが連結でなければならないとき、高橋君が得られる報酬の最大値を求めてください。

制約

2 \leq N \leq 2\times 10^5
N-1 \leq M \leq 2\times 10^5
1 \leq A_i,B_i \leq N
-10^9 \leq C_i \leq 10^9
与えられるグラフは連結である
入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

出力

答えを出力せよ。

入力例 1

出力例 1

辺 4,5 を取り除くことで合計 4 の報酬を得られます。これより多くの報酬を得ることはできないため、答えは 4 となります。

入力例 2

出力例 2

報酬が負であるような辺が存在することもあります。

入力例 3

出力例 3

多重辺や自己ループが存在することもあります。

Score : 500 points

Problem Statement

We have a connected undirected graph with N vertices and M edges.
The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i connects Vertices A_i and B_i.

Takahashi is going to remove zero or more edges from this graph.

When removing Edge i, a reward of C_i is given if C_i \geq 0, and a fine of |C_i| is incurred if C_i<0.

Find the maximum total reward that Takahashi can get when the graph must be connected after removing edges.

Constraints

2 \leq N \leq 2\times 10^5
N-1 \leq M \leq 2\times 10^5
1 \leq A_i,B_i \leq N
-10^9 \leq C_i \leq 10^9
The given graph is connected.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

Output

Print the answer.

Sample Input 1

Sample Output 1

Removing Edges 4 and 5 yields a total reward of 4. You cannot get any more, so the answer is 4.

Sample Input 2

Sample Output 2

There may be edges that give a negative reward when removed.

Sample Input 3

Sample Output 3

There may be multi-edges and self-loops.

I - More Holidays

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

o と x からなる長さ N の文字列 S と、整数 M,K が与えられます。
S には少なくとも 1 つの x が含まれることが保証されます。

S を M 個連結して得られる長さ NM の文字列を T とします。 T に含まれる x のうち丁度 K 個を選んで o に変えることを考えます。
あなたの目標は、変更後の T に o のみからなるできるだけ長い連続部分文字列が含まれるようにすることです。
o のみからなる連続部分文字列の長さとして達成可能な最大値を求めてください。

制約

N,M,K は整数
1 \le N \le 3 \times 10^5
1 \le M \le 10^9
x を文字列 T に含まれる x の総数としたとき、 1 \le K \le x
S は o と x からなる長さ N の文字列
S には少なくとも 1 つの x が含まれる

入力

入力は以下の形式で標準入力から与えられる。

N M K
S

出力

答えを整数として出力せよ。

入力例 1

10 1 2
ooxxooooox

出力例 1

S= ooxxooooox 、 T= ooxxooooox です。
3 文字目と 4 文字目の x を o に変更することにより、変更後の T= ooooooooox となります。
このとき o のみからなる長さ 9 の連続部分文字列が得られ、これが達成可能な最大値です。

入力例 2

5 3 4
oxxox

出力例 2

S= oxxox 、 T= oxxoxoxxoxoxxox です。
5,7,8,10 文字目の x を o に変更することにより、変更後の T= oxxooooooooxxox となります。
このとき o のみからなる長さ 8 の連続部分文字列が得られ、これが達成可能な最大値です。

入力例 3

30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox

出力例 3

19964887064

Score : 500 points

Problem Statement

You are given a string S of length N consisting of o and x, and integers M and K.
S is guaranteed to contain at least one x.

Let T be the string of length NM obtained by concatenating M copies of S. Consider replacing exactly K x's in T with o.
Your objective is to have as long a contiguous substring consisting of o as possible in the resulting T.
Find the maximum length of a contiguous substring consisting of o that you can obtain.

Constraints

N, M, and K are integers.
1 \le N \le 3 \times 10^5
1 \le M \le 10^9
1 \le K \le x, where x is the number of x's in the string T.
S is a string of length N consisting of o and x.
S has at least one x.

Input

The input is given from Standard Input in the following format:

N M K
S

Output

Print the answer as an integer.

Sample Input 1

10 1 2
ooxxooooox

Sample Output 1

S= ooxxooooox and T= ooxxooooox.
Replacing x at the third and fourth characters with o makes T= ooooooooox.
Now we have a length-9 contiguous substring consisting of o, which is the longest possible.

Sample Input 2

5 3 4
oxxox

Sample Output 2

S= oxxox and T= oxxoxoxxoxoxxox.
Replacing x at the 5,7,8 and 10-th characters with o makes T= oxxooooooooxxox.
Now we have a length-8 contiguous substring consisting of o, which is the longest possible.

Sample Input 3

30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox

Sample Output 3

19964887064