Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 266 点
問題文
高橋君は学校の図書館で司書のアルバイトをしています。
図書館には N 種類の本があり、それぞれの本には 1 から N までの管理番号が付けられています。管理番号 i の本の現在の蔵書数は A_i 冊です。
今日、 M 件の貸出申請が届きました。 j 番目の貸出申請では、管理番号 B_j の本を C_j 冊貸し出すよう求められています。
高橋君は各貸出申請を j = 1, 2, \ldots, M の順に処理します。各貸出申請を処理する際、対象の本の現在の蔵書数が申請された冊数以上であれば、蔵書数から申請された冊数を差し引きます。蔵書数が申請された冊数未満の場合は、その貸出申請はスキップされ、蔵書数は変化しません。
すべての貸出申請を処理した後、各本の最終的な蔵書数を求めてください。
制約
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq B_j \leq N (1 \leq j \leq M)
- 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
- 入力はすべて整数である
入力
N M A_1 A_2 \ldots A_N B_1 C_1 B_2 C_2 \vdots B_M C_M
- 1 行目には、本の種類数を表す N と、貸出申請の件数を表す M が、スペース区切りで与えられる。
- 2 行目には、各本の初期蔵書数を表す A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
- 続く M 行にわたって、貸出申請の情報が与えられる。
- 2 + j 行目 (1 \leq j \leq M) には、 j 番目の貸出申請で対象となる管理番号 B_j と、貸し出す冊数 C_j が、スペース区切りで与えられる。
出力
すべての貸出申請を処理した後の、各本の最終的な蔵書数を、管理番号 1 から管理番号 N の順にスペース区切りで 1 行で出力してください。
入力例 1
3 4 5 3 2 1 2 2 1 1 4 3 3
出力例 1
3 2 2
入力例 2
5 6 10 5 8 3 7 3 4 1 10 2 5 3 5 4 3 4 1
出力例 2
0 0 4 0 7
入力例 3
8 10 1000000000 500 100 250 999999999 1 50 300 1 999999999 1 1 5 1000000000 6 1 6 1 3 50 3 50 3 1 7 25 8 301
出力例 3
0 500 0 250 999999999 0 25 300
Score : 266 pts
Problem Statement
Takahashi is working a part-time job as a librarian at his school's library.
The library has N types of books, each assigned a catalog number from 1 to N. The current stock of the book with catalog number i is A_i copies.
Today, M lending requests have been received. The j-th lending request asks to lend out C_j copies of the book with catalog number B_j.
Takahashi processes each lending request in the order j = 1, 2, \ldots, M. When processing each lending request, if the current stock of the requested book is greater than or equal to the requested number of copies, the requested number of copies is subtracted from the stock. If the stock is less than the requested number of copies, the lending request is skipped and the stock remains unchanged.
After processing all lending requests, determine the final stock of each book.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq B_j \leq N (1 \leq j \leq M)
- 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
- All input values are integers
Input
N M A_1 A_2 \ldots A_N B_1 C_1 B_2 C_2 \vdots B_M C_M
- The first line contains N, the number of types of books, and M, the number of lending requests, separated by a space.
- The second line contains A_1, A_2, \ldots, A_N, the initial stock of each book, separated by spaces.
- The following M lines contain the lending request information.
- The (2 + j)-th line (1 \leq j \leq M) contains the catalog number B_j and the number of copies C_j for the j-th lending request, separated by a space.
Output
After processing all lending requests, output the final stock of each book in a single line, in order from catalog number 1 to catalog number N, separated by spaces.
Sample Input 1
3 4 5 3 2 1 2 2 1 1 4 3 3
Sample Output 1
3 2 2
Sample Input 2
5 6 10 5 8 3 7 3 4 1 10 2 5 3 5 4 3 4 1
Sample Output 2
0 0 4 0 7
Sample Input 3
8 10 1000000000 500 100 250 999999999 1 50 300 1 999999999 1 1 5 1000000000 6 1 6 1 3 50 3 50 3 1 7 25 8 301
Sample Output 3
0 500 0 250 999999999 0 25 300
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君は山道をハイキングしている。山道には一列に並んだ N 個の地点があり、順に地点 1, 地点 2, \ldots, 地点 N と番号が付いている。地点 i の標高は A_i である。
高橋君は地点 1 から出発し、地点 N に到達したい。高橋君は地点番号が増加する方向にのみ進むことができ、地点 i にいるとき、地点 i + 1（i + 1 \leq N のとき）または地点 i + 2（i + 2 \leq N のとき）のいずれかに進むことができる。
地点 i から地点 i+1 または地点 i+2 に進むとき、移動先の地点の標高を A_j とすると、疲労が \max(A_j - A_i, 0) だけ加算される。すなわち、移動先の標高が現在地より高い場合はその標高差が疲労となり、そうでない場合は疲労の加算は 0 である。
高橋君が地点 1 から地点 N まで移動するときの、疲労の合計の最小値を求めてください。ただし、出発時の疲労は 0 とする。
制約
- 2 \leq N \leq 5 \times 10^5
- 0 \leq A_i \leq 10^9（1 \leq i \leq N）
- 入力はすべて整数である。
入力
N A_1 A_2 \cdots A_N
1 行目には、地点の数を表す整数 N が与えられる。2 行目には、各地点の標高を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
出力
高橋君が地点 1 から地点 N まで移動するために必要な疲労の合計の最小値を 1 行で出力せよ。
入力例 1
4 10 30 20 25
出力例 1
15
入力例 2
5 8 6 7 3 2
出力例 2
0
入力例 3
10 5 12 4 20 7 15 3 18 6 10
出力例 3
10
入力例 4
20 100 180 120 250 130 300 90 200 80 260 140 400 150 350 170 500 160 450 190 210
出力例 4
170
入力例 5
2 1000000000 0
出力例 5
0
Score : 333 pts
Problem Statement
Takahashi is hiking along a mountain trail. The trail has N points arranged in a line, numbered sequentially as point 1, point 2, \ldots, point N. The elevation of point i is A_i.
Takahashi starts at point 1 and wants to reach point N. He can only move in the direction of increasing point numbers. When he is at point i, he can move to either point i + 1 (if i + 1 \leq N) or point i + 2 (if i + 2 \leq N).
When moving from point i to point i+1 or point i+2, if the elevation of the destination point is A_j, then fatigue of \max(A_j - A_i, 0) is accumulated. In other words, if the destination's elevation is higher than the current location, the elevation difference becomes fatigue; otherwise, the fatigue added is 0.
Find the minimum total fatigue when Takahashi travels from point 1 to point N. The initial fatigue at departure is 0.
Constraints
- 2 \leq N \leq 5 \times 10^5
- 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers.
Input
N A_1 A_2 \cdots A_N
The first line contains an integer N representing the number of points. The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the elevation of each point.
Output
Print on a single line the minimum total fatigue required for Takahashi to travel from point 1 to point N.
Sample Input 1
4 10 30 20 25
Sample Output 1
15
Sample Input 2
5 8 6 7 3 2
Sample Output 2
0
Sample Input 3
10 5 12 4 20 7 15 3 18 6 10
Sample Output 3
10
Sample Input 4
20 100 180 120 250 130 300 90 200 80 260 140 400 150 350 170 500 160 450 190 210
Sample Output 4
170
Sample Input 5
2 1000000000 0
Sample Output 5
0
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は果物農園で収穫されたりんごの箱詰め作業を担当しています。収穫された N 個のりんごを K 個の箱に分けて出荷することになりました。
それぞれのりんごには重さが測定されており、i 番目 (1 \leq i \leq N) のりんごの重さは A_i グラムです。
出荷先からは、品質管理のため以下の条件を満たす箱詰めを行うよう依頼されています：
- N 個のりんごそれぞれをちょうど 1 つの箱に入れ、どの箱にも少なくとも 1 個のりんごが入るようにする。
- 各箱について、その箱に入っているりんごの重さの最大値と最小値の差を「箱のばらつき度」と呼ぶ。りんごが 1 個だけ入っている箱のばらつき度は 0 とする。
高橋君は、K 個すべての箱のばらつき度の合計をできるだけ小さくしたいと考えています。
条件を満たすようにりんごを箱に分けるとき、すべての箱のばらつき度の合計の最小値を求めてください。
制約
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N K A_1 A_2 \ldots A_N
1 行目には、りんごの個数を表す整数 N と箱の数を表す整数 K が、スペース区切りで与えられます。
2 行目には、各りんごの重さを表す N 個の整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられます。
出力
すべての箱のばらつき度の合計の最小値を 1 行で出力してください。
入力例 1
5 2 3 1 4 1 5
出力例 1
2
入力例 2
8 3 10 25 12 30 15 28 11 22
出力例 2
10
入力例 3
15 4 100 250 180 300 120 275 190 310 105 260 175 295 130 280 200
出力例 3
100
Score : 366 pts
Problem Statement
Takahashi is in charge of packing apples harvested at a fruit farm into boxes. He needs to distribute N harvested apples into K boxes for shipment.
The weight of each apple has been measured, and the weight of the i-th (1 \leq i \leq N) apple is A_i grams.
The shipping destination has requested that the packing satisfy the following conditions for quality control:
- Each of the N apples must be placed into exactly 1 box, and every box must contain at least 1 apple.
- For each box, the difference between the maximum and minimum weight of the apples in that box is called the "variation" of the box. The variation of a box containing only 1 apple is 0.
Takahashi wants to minimize the total variation across all K boxes.
Given that the apples are distributed into boxes satisfying the conditions, find the minimum possible total variation across all boxes.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- All inputs are integers
Input
N K A_1 A_2 \ldots A_N
The first line contains an integer N representing the number of apples and an integer K representing the number of boxes, separated by a space.
The second line contains N integers A_1, A_2, \ldots, A_N representing the weight of each apple, separated by spaces.
Output
Print the minimum possible total variation across all boxes in a single line.
Sample Input 1
5 2 3 1 4 1 5
Sample Output 1
2
Sample Input 2
8 3 10 25 12 30 15 28 11 22
Sample Output 2
10
Sample Input 3
15 4 100 250 180 300 120 275 190 310 105 260 175 295 130 280 200
Sample Output 3
100
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は N 人の選手を 2 つのチームに分けて綱引きの試合を行おうとしています。i 番目の選手の力は A_i です。
N 人の選手それぞれをチーム 1 またはチーム 2 のいずれかに割り当てます。すべての選手はちょうど一方のチームに属さなければなりません。ただし、一方のチームの人数が 0 人であっても構いません。
チーム 1 に属する選手の力の合計を S_1、チーム 2 に属する選手の力の合計を S_2 とします。S_1 + S_2 は全選手の力の総和で一定なので、\min(S_1, S_2) を最大化することは |S_1 - S_2| を最小化することと同値です。試合をできるだけ拮抗させるために、\min(S_1, S_2) の最大値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^4
- 1 \leq A_i \leq 2 \times 10^5 \quad (1 \leq i \leq N)
- \displaystyle \sum_{i=1}^{N} A_i \leq 2 \times 10^5
- 入力はすべて整数である
入力
N A_1 A_2 : A_N
- 1 行目には、選手の人数を表す整数 N が与えられる。
- 続く N 行のうち i 行目には、i 番目の選手の力を表す整数 A_i が与えられる。
出力
\min(S_1, S_2) の最大値を整数で 1 行に出力してください。
入力例 1
4 1 2 3 4
出力例 1
5
入力例 2
3 2 5 8
出力例 2
7
入力例 3
12 13 7 11 2 9 4 8 6 5 10 3 12
出力例 3
45
入力例 4
20 12000 11500 11000 10500 10000 9500 9000 8500 8000 7500 7000 6500 6000 5500 5000 4500 4000 3500 3000 2500
出力例 4
72500
入力例 5
1 200000
出力例 5
0
Score : 400 pts
Problem Statement
Takahashi wants to divide N players into 2 teams to hold a tug-of-war match. The strength of the i-th player is A_i.
Each of the N players is assigned to either Team 1 or Team 2. Every player must belong to exactly one team. However, it is allowed for one of the teams to have 0 members.
Let S_1 be the total strength of the players belonging to Team 1, and S_2 be the total strength of the players belonging to Team 2. Since S_1 + S_2 is constant (the total strength of all players), maximizing \min(S_1, S_2) is equivalent to minimizing |S_1 - S_2|. To make the match as competitive as possible, find the maximum value of \min(S_1, S_2).
Constraints
- 1 \leq N \leq 2 \times 10^4
- 1 \leq A_i \leq 2 \times 10^5 \quad (1 \leq i \leq N)
- \displaystyle \sum_{i=1}^{N} A_i \leq 2 \times 10^5
- All inputs are integers
Input
N A_1 A_2 : A_N
- The first line contains an integer N representing the number of players.
- The i-th of the following N lines contains an integer A_i representing the strength of the i-th player.
Output
Output the maximum value of \min(S_1, S_2) as an integer on a single line.
Sample Input 1
4 1 2 3 4
Sample Output 1
5
Sample Input 2
3 2 5 8
Sample Output 2
7
Sample Input 3
12 13 7 11 2 9 4 8 6 5 10 3 12
Sample Output 3
45
Sample Input 4
20 12000 11500 11000 10500 10000 9500 9000 8500 8000 7500 7000 6500 6000 5500 5000 4500 4000 3500 3000 2500
Sample Output 4
72500
Sample Input 5
1 200000
Sample Output 5
0
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 466 点
問題文
高橋君は洗濯物を片付けています。洗濯カゴの中には N 枚の靴下があり、それぞれ 1 から N の番号が付けられています。靴下 i の色の濃さは S_i です。
高橋君はこれらの靴下からちょうど M 組のペアを作りたいと考えています。具体的には、N 枚の靴下の中から 2M 枚を選び、それらを M 組の2枚ずつのペアに分けます。選ばれなかった靴下はどのペアにも属しません。
各ペアの「違和感」は、そのペアを構成する2枚の靴下の色の濃さの差の絶対値で定義されます。すなわち、靴下 i と靴下 j がペアになったとき、そのペアの違和感は |S_i - S_j| です。
M 組のペアの違和感の合計の最小値を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq \lfloor N/2 \rfloor
- 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数である
入力
N M S_1 S_2 \ldots S_N
- 1 行目には、靴下の枚数を表す整数 N と、作りたいペアの数を表す整数 M が、スペース区切りで与えられる。
- 2 行目には、各靴下の色の濃さを表す整数 S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
出力
M 組のペアを作ったときの違和感の合計の最小値を 1 行で出力せよ。
入力例 1
4 2 1 5 3 4
出力例 1
3
入力例 2
5 2 10 1 20 2 11
出力例 2
2
入力例 3
12 5 8 3 15 20 14 9 30 1 2 25 24 16
出力例 3
8
入力例 4
30 12 100 5 200 201 50 52 53 1000 999 998 300 305 700 701 702 10 11 12 400 410 600 590 591 800 805 806 1 2 3 4
出力例 4
29
入力例 5
2 1 1 1000000000
出力例 5
999999999
Score : 466 pts
Problem Statement
Takahashi is putting away his laundry. There are N socks in the laundry basket, numbered 1 through N. The color intensity of sock i is S_i.
Takahashi wants to form exactly M pairs from these socks. Specifically, he selects 2M socks out of the N socks and divides them into M pairs of two socks each. The socks that are not selected do not belong to any pair.
The "discomfort" of each pair is defined as the absolute difference in color intensity between the two socks forming that pair. That is, when sock i and sock j are paired, the discomfort of that pair is |S_i - S_j|.
Find the minimum possible total discomfort of the M pairs.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq \lfloor N/2 \rfloor
- 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers
Input
N M S_1 S_2 \ldots S_N
- The first line contains an integer N representing the number of socks and an integer M representing the number of pairs to be formed, separated by a space.
- The second line contains integers S_1, S_2, \ldots, S_N representing the color intensity of each sock, separated by spaces.
Output
Print in one line the minimum possible total discomfort when forming M pairs.
Sample Input 1
4 2 1 5 3 4
Sample Output 1
3
Sample Input 2
5 2 10 1 20 2 11
Sample Output 2
2
Sample Input 3
12 5 8 3 15 20 14 9 30 1 2 25 24 16
Sample Output 3
8
Sample Input 4
30 12 100 5 200 201 50 52 53 1000 999 998 300 305 700 701 702 10 11 12 400 410 600 590 591 800 805 806 1 2 3 4
Sample Output 4
29
Sample Input 5
2 1 1 1000000000
Sample Output 5
999999999