시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 60 | 18 | 18 | 50.000% |
상근이와 친구들은 놀이 공원에 놀러갔다. 이 놀이 공원에는 많은 종류의 롤러코스터가 있고, 상근이는 각 롤러코스터를 미리 분석해 왔다. 상근이는 각 롤러코스터를 탔을 때 느낄 수 있는 재미를 숫자로 적어왔다. 하지만, 롤러코스터를 탈 때 마다 느끼는 재미는 점점 떨어진다.
상근이는 i번 롤러코스터를 k번째로 탔을 때 느끼는 재미를 함수로 정의해 왔다. f(i, k) = ai - (k-1)2*bi. 만약 f(i,k)값이 양수가 아니라면, 그 롤러코스터를 타면, 더이상 재미를 느끼지 않는 것이다.
상근이는 재미의 합이 최대가 되게 롤러코스터를 타려고 한다.
첫째 줄에 N이 주어진다. N은 놀이 공원에 있는 롤러코스터의 개수이다. (0 < N ≤ 100)
다음 N개의 줄에는 ai, bi, ti가 있다. ai와 bi는 상근이가 정의한 함수의 계수이고, ti는 i번째 롤러코스터를 타는데 걸리는 시간이다. (0 ≤ ai, bi ≤ 1,000, 0 < ti ≤ 25,000)
다음 줄에는 놀이 공원을 방문하는 시간의 개수 Q가 주어진다. (0 ≤ Q ≤ 1,000) 다음 Q개 줄에는 상근이가 놀이 공원에 방문하는 시간 Ti가 주어진다. (0 ≤ Ti ≤ 25,000)
출력은 Q개의 줄을 출력한다. 각각의 시간 Ti에 대해서, 상근이가 느낄 수 있는 최대 재미 점수를 출력한다.
2 5 0 5 7 0 7 4 88 5 6 7
88 5 5 7
1 100 3 2 5 2 3 4 5 100
100 100 197 197 435
ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2012 F번