레이팅 미적용*참고: 이 문제의 시간 제한은 기본값의 1.5배인 3초이다. 메모리 제한은 기본값의 두 배인 512MB이다.*
베시는 \(N\)문항짜리 OX 시험을 치르고 있다(\(1\le N\le 2\cdot 10^5\)). \(i\)번째 문제를 맞히면 \(a_i\)점을 얻고, 틀리면 \(b_i\)점을 잃으며, 답하지 않으면 점수 변화가 없다(\(0
베시는 똑똑한 소라서 모든 답을 알고 있지만, 시험을 감독하는 엘시가 시험이 끝난 뒤 최대 \(k\)개의 문제를 소급하여 바꿔서 베시가 그 문제들을 맞히지 못하게 만들까 봐 걱정하고 있다.
\(k\)(\(0\le k\le N\))의 후보 값 \(Q\)개(\(1\le Q\le N+1\))가 주어질 때, 각 \(k\)에 대해 베시가 보장할 수 있는 점수를 구하시오. 단, 베시는 최소 \(k\)개의 문제에 답해야 한다.
Problem credits: Benjamin Qi
배점
- 입력 2-4: \(N\le 100\)
- 입력 5-7: \(Q\le 10\), \(N\le 2\cdot 10^5\)
- 입력 7-20: 추가 제약이 없다.
Problem credits: Benjamin Qi
첫째 줄에 \(N\)과 \(Q\)가 주어진다.
다음 \(N\)개의 줄에 각각 \(a_i\)와 \(b_i\)가 주어진다.
다음 \(Q\)개의 줄에 각각 \(k\)의 값이 주어진다. 어떤 \(k\) 값도 두 번 이상 나타나지 않는다.
각 \(k\)에 대한 답을 별도의 줄에 출력한다.
2 3
3 1
4 2
2
1
0-3
1
7For each value of \(k\), it is optimal for Bessie to answer all of the questions.
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > February > Platinum