Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋くん一家では今シーズンの果物がみかんに決まり、K個のみかんを買うことが決まりました。 みかんは1個A円、さらにL個のセットでB円で売っています。 1個のみかんとL個のセットをそれぞれいくつか買い、合計でK個以上のみかんを買うとき、払うお金の最小値を求めるプログラムを書いてください。
制約
- 1 ≦ A, B, K ≦ 10^9
- 2 ≦ L ≦ 10^9
- B ≦ A*L
入力
入力は以下の形式で標準入力から与えられる。
A B K L
出力
1行目に、少なくともK個のみかんを買うために必要なお金を出力せよ。
入力例1
3 7 10 3
出力例1
24
3個のセットを3つ、1個のみかんを1つ買うと合計24円となる。これより安く10個のみかんを買う方法はない。
入力例2
4 5 11 3
出力例2
20
3個のセットを4つ買うのが最適である。
入力例3
3 8 3 3
出力例3
8
入力例4
3 8 2 3
出力例4
6
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
駐車場でN人が車を駐めようとしています。 駐車場はN個の駐車スペースがあり1からNまで番号付けられています。また、2つの駐車スペースを双方向に結ぶ道がM本あり、i番目の道はu_i番目の駐車スペースとv_i番目の駐車スペースを結んでいます。 駐車スペースSは駐車場の入り口とつながっています。
i番目の人は、どういうわけかi番目の駐車スペースにしか車を駐めたくないようです。このため、駐車場の入り口から、まだ誰も車を駐めていない駐車スペースとそれらを結ぶ道を通ってi番目の駐車スペースに行くことができないとき、車を駐めずに帰ってしまいます。
1番目の人からN番目の人まで順番に駐車場にやってきます。最終的に駐車場に駐める人の番号を昇順に出力してください。
制約
- 1 ≦ N, M ≦ 2*10^5
- 1≦u_i, v_i≦N
- u_i ≠ v_i
- 1 ≦ S ≦ N
- 全ての駐車スペースへは、入り口から道と駐車スペースを経由してたどり着くことができる
部分点
- M ≦ 2,000 を満たすテストケース全てに正解した場合、部分点として40点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
N M S u_1 v_1 : u_M v_M
出力
最終的に駐車場に駐める人の番号を昇順に1行ずつ出力せよ。
入力例1
3 3 2 1 2 2 3 1 3
出力例1
1 2
1番目の車は、駐車スペース1に行くことができるためそこに駐めます。 2番目の車は、駐車スペース2に行くことができるためそこに駐めます。 3番目の車は、2番目の車に塞がれ駐車スペース3に行くことができないため、帰ります。
入力例2
5 6 5 1 5 3 5 3 2 4 1 1 2 4 3
出力例2
1 2 3 5
青い円を空いている駐車スペース、赤い円を車のいる駐車スペースとすると、上図のような順番で駐車スペースが埋まっていき、4番目の車は駐めることができません。
入力例3
5 5 5 1 4 4 3 3 2 2 5 5 1
出力例3
1 2 5
Time Limit: 3 sec / Memory Limit: 256 MB
問題文
高橋くんのいる会社はN人の社員からなる。社員iと社員jの間には、信頼度w_{i,j}が定まっている。 おかげ様で会社はぐんぐん成長したため、N人をいくつかの部門に分けることになった。ここで、部門分けのスコアを、(部門の数)*K-(異なる部門に属する2人の間の信頼度の総和)と定める。 スコアの最大値を求めるプログラムを書いてください。
制約
- 1 ≦ N ≦ 17
- i≠j のとき、 1 ≦ w_{i,j} ≦ 10^6
- w_{i,i} = 0
- w_{i,j}=w_{j,i}
- 1 ≦ K ≦ 10^6
- 入力はすべて整数である
部分点
- N ≦ 9 を満たすテストケース全てに正解した場合、部分点として40点が与えられる。
- N ≦ 15 を満たすテストケース全てに正解した場合、部分点として追加で40点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
N K
w_{1,1} ... w_{1,N}
:
w_{N,1} ... w_{N,N}
出力
1行目に、スコアの最大値を出力せよ。
入力例1
3 3 0 1 5 1 0 1 5 1 0
出力例1
4
社員1と3で1つの部門、社員2で1つの部門を作ると、 部門の数は2つ、異なる部門の間の2人の信頼度の総和は2なので、2*3-2=4となる。 スコアを4より大きくする方法はない。
入力例2
4 8 0 2 3 5 2 0 1 2 3 1 0 8 5 2 8 0
出力例2
11
入力例3
5 10 0 10 1 2 1 10 0 1 2 1 1 1 0 6 7 2 2 6 0 8 1 1 7 8 0
出力例3
12
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
あなたは風変わりなバーに来ています。このバーでは、N種類のドリンクがあり、あなたは初めにN個のグラスを与えられます。i番目のグラスはi番目のドリンクに対応しており、i番目のドリンクのみが注がれます。また、それぞれのドリンクに対し、美味しさw_iが定まっています。初めに、全てのグラスは空です。
それぞれのドリンクは、何回か決まった時刻に補充されます。 すなわち、 時間t_{i,j}(1≦j≦M_i)にi番目のグラスが空ならば、i番目のグラスにi番目のドリンクが注がれます。
あなたは、好きな奇数時刻に、全てのグラスに入っているドリンクを全て飲み干すことができます。一部のドリンクのみを飲む行為は禁止されています。 飲んだドリンクの美味しさの総和の最大値を求めるプログラムを書いてください。ただし、同じドリンクを複数回飲んだときも、美味しさは重複して計算されることに注意してください。
制約
- 1 ≦ N ≦ 5*10^5
- 2 ≦ t_{i,j} ≦ 10^6
- t_{i,j} < t_{i,j+1}
- t_{i,j}は偶数である
- Σ M_i ≦ 5*10^5
- 1 ≦ M_i
- -10^9 ≦ w_i ≦ 10^9
部分点
- t_{i,j} ≦ 1,000 かつ N ≦ 1,000 を満たすテストケース全てに正解した場合、部分点として30点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
N
w_1 ... w_N
M_1 t_{1,1} ... t_{1,M_1}
:
M_N t_{N,1} ... t_{N,M_N}
出力
1行目に、美味しさの総和を出力せよ。
入力例1
3 2 5 -6 1 2 2 4 10 2 4 8
出力例1
6
時刻9と11にグラスにあるドリンクを全て飲み干します。 時刻9では、3つ全てドリンクが注がれているため、美味しさ2+5-6=1を得ます。 時刻11では、2番目のドリンクのみ注がれているため、美味しさ5を得ます。合計6となります。
入力例2
3 2 5 -6 2 2 8 2 4 10 2 4 10
出力例2
3
入力例3
3 3 5 -4 2 2 8 4 4 6 10 12 4 2 4 8 10
出力例3
18
入力例4
3 -2 -2 -2 2 2 8 4 4 6 10 12 4 2 4 8 10
出力例4
0