#P18068. GPA Optimization Plan

GPA Optimization Plan

GPA Optimization Plan

题目描述

成绩单上有 nn 门课程,分属 mm 个学期。第 ii 门课的学分、绩点和所属学期分别为 si,gi,tis_i,g_i,t_i。

每个学期可以选择至多一门课程,将其改为 PNP 模式,也可以不选择。选择 PNP 的课程不参与平均绩点计算。若参与计算的课程集合为 RR,则平均绩点为

$$\operatorname{GPA}(R)=\frac{\sum_{i\in R}s_i g_i}{\sum_{i\in R}s_i}.$$

保证前 2m2m 门课满足 ti=⌊(i+1)/2⌋t_i=\lfloor(i+1)/2\rfloor,即每个学期最初都有两门课。

对每个 k=2m,2m+1,…,nk=2m,2m+1,\ldots,n,只考虑成绩单的前 kk 门课,求选择 PNP 课程后能够得到的最大 GPA。不同 kk 的选择相互独立。

输入格式

第一行整数 TT,表示测试用例数。每组数据第一行两个整数 n,mn,m,接下来 nn 行每行三个整数 si,gi,tis_i,g_i,t_i。

1≤T≤1041\le T\le10^4,1≤m≤81\le m\le8,2m≤n≤1052m\le n\le10^5,1≤si,gi≤1051\le s_i,g_i\le10^5,1≤ti≤m1\le t_i\le m。每组均满足上述前 2m2m 门课的学期限制。所有测试用例的 nn 之和不超过 3×1053\times10^5。

输出格式

每组数据输出 n−2m+1n-2m+1 行,依次表示各个前缀的最大 GPA。

若输出为 xx、标准答案为 yy,须满足 ∣x−y∣/max⁡(1,∣y∣)≤10−6|x-y|/\max(1,|y|)\le10^{-6}。

样例 1

输入

2
5 1
9 7 1
1 2 1
9 6 1
6 4 1
4 7 1
9 2
9 1 1
9 9 1
1 9 2
4 4 2
6 10 1
8 6 2
2 7 1
8 6 2
6 5 1

输出

7.0000000000
6.5000000000
6.2631578947
6.3913043478
9.0000000000
9.3750000000
8.3000000000
8.1818181818
7.6470588235
7.2500000000