AOJ 5/30

2014-05-30 | [Competitive programming]

1314

本当に,問題文で指示されたとおりにパーサを実装する.効率とかはほとんど考えなくても通る.面倒なだけ (300 行超えた)

2374

m_i, n_i をソートする.m_i は降順,n_i は昇順とする. m_i の先頭 i 個の要素に対応する (i 個の) 種類のにんじんを用いて食事をとることのできるうさぎの数の最大数は, Σmin(n_j, i) である.これは i に対して単調に増加する.

この数を k とする.m_i に対応する種類のにんじんを用いて新たに食事が可能になるうさぎの数は, min(m_i, k - (現在食事しているうさぎの数)) である. これの和を順次取ればよい. Σmin(n_j, i) は,n_j が i 以下であるような境界を順次動かして和を動的に変化させると求められる.