質問する

2019年、アジア大学プログラミングコンテスト(Ajou Programming Contest,APC)も予定通り開催されました!今年APC総監を新たに務めた俊表は、大会の出題過程で大きな悩みに陥った.APCに参加する参加者が多すぎるため、大会問題の難易度設定が難しい.
APCにはプログラミング大会に慣れていない学生や非専門の学生が多く参加するため、誰もが解いたり挑戦したりできる難易度曲線が必要だ.「京仁地区6大学合同プログラミングコンテスト揺れ!10人が出場する学校代表を選抜するためには、代表選考会の弁別能力を備え、外部から単独で参加できるオープンコンテストも行わなければならないため、1時間足らずでいわゆる「水たまり」たちに征服された.また、APCの出題者である俊表、万英、賢貞、俊書は問題を準備するのに苦労しているので、参加者はすべての問題を一度読んでほしい.
欲望に満ちた俊表は熟考を経て、無数のNIZを満たすための解決策を提案した.1つの問題を制限条件で単純バージョンと困難バージョンに分け,単純バージョンのみに合致しても一部の点数のサブタスク問題に大会を構成する.また,このように生成された問題を単純バージョンの難易度順に手配する.
このように問題を準備すれば、プログラミングコンテストに慣れていない人は前から挑戦して、時間をかけて容易な問題を探すことなく、難しいバージョンで学校代表を選抜する弁別力を維持することができ、出題チームがすべての問題を読むことを望んでいることを実現することができます.

例<図1>出題時に評価した問題の難易度(例2)
ヒョンジョンはAPCに一度行ってみたいという願いがある.しかし、この願いは今まで一度もなかったし、これからも叶わないので、賢貞は口癖のようなことを言った...

賢静:あ~~APCに参加すればボーナスがもらえるよ~

俊表:...違うようですね?

ヒョンジョンは根拠のない自信に呆然として、出題時に評価した問題の難易度を通じて、ヒョンジョンの予想点数を教え、ヒョンジョンが現実を受け入れるのを助けることを望んでいる.
ヒョンジョンはLほどの力を持っていて、L以下の難易度の問題を解くことができる.また、賢智はコードが遅いため、試合時間が足りず、Kより多くの問題を解決することができなかった.ある問題に対して、もしあなたが簡単なバージョンを解決したら、あなたは100点を得ることができます;もしあなたが困難なバージョンを解決したら、あなたはここで40点を得て、140点を得ることができます.問題を解決するバージョンは、単純なバージョンを解決するように問題を解決するため、問題を解決するように計算されます.
ヒョンジョンがAPCに参加すれば、最多得点を教えてあげる.
入力
1行目は問題の個数N,賢智の力L,賢智が大会で解答できる問題の最大個数Kを与える.
2行目からN行目に1~N問目の単純バージョンの難易度sub 1,難易度バージョンの難易度sub 2が順に与えられる.
しゅつりょく
賢智がAPCに参加すると、得られた点数の最大値が出力されます.
制限
1 ≤ N ≤ 100
1 ≤ L ≤ 50
1 ≤ sub1 ≤ sub2 ≤ 50
入力例1
4 8 4
1 8
4 5
6 20
9 12
サンプル出力1
380

1번, 2번 문제의 어려운 버전을 해결해 2×140 = 280점을, 3번 문제의 쉬운 버전을 해결해 100점을 얻어 총 380점을 얻는다.

현정이가 4문제를 풀 수 있을 정도로 대회 시간은 충분하지만, 4번 문제는 현정이에겐 너무 어려워서 풀 수 없다.

入力例2
8 7 5
1 3
2 5
3 5
4 8
5 8
6 9
6 7
7 10
サンプル出力2
660
入力例3
8 9 5
1 8
3 10
4 5
5 20
7 12
8 15
9 50
14 14
サンプル出力3
580

解法

2 Dリスト、行は問題を表し、列は各問題の難易度を表します.
難易度は難易度でソートされ、難易度がL以下の場合はスコアが累積されて解かれるため、要素はキャンセルされます.
Kが0以上の難易度になると、終了する.
簡単なバージョンの難易度を基準にソートします.
同様に行い,累積した値が正解となる.

コード#コード#

N, L, K = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(N)]
result = 0

data.sort(key=lambda x: x[1])
while K > 0:
    if data[0][1] > L:
        break
    else:
        result += 140
        data.pop(0)
        K -= 1

data.sort(key=lambda x: x[0])
while K > 0:
    if data[0][0] > L:
        break
    else:
        result += 100
        data.pop(0)
        K -= 1

print(result)

白駿17224 APCはなぜサブミッション大会になったのですか?