跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#CF2000E. Photoshoot for Gorillas

Photoshoot for Gorillas

题目描述

有一个 nn 行 mm 列的网格,以及 ww 只身高分别为 a1,…,awa_1,\ldots,a_w 的大猩猩。将全部大猩猩放进网格,每格至多放一只,其余格子为空。

对网格中每个完整的、边长为 kk 的正方形子网格,计算其中所有大猩猩的身高之和,再将这些和全部相加,得到总观赏值。求总观赏值的最大可能值。

输入格式

第一行输入测试组数 tt。每组数据包含三行:第一行输入 n,m,kn,m,k;第二行输入 ww;第三行输入 ww 个身高 aia_i。

输出格式

每组数据输出一行,包含一个整数,表示最大的总观赏值。

数据范围

1≤t≤10001\le t\le1000;1≤n,m≤2×1051\le n,m\le2\times10^5;1≤nm≤2×1051\le n m\le2\times10^5;1≤k≤min⁡(n,m)1\le k\le\min(n,m);1≤w≤nm1\le w\le n m;1≤ai≤1091\le a_i\le10^9。

同一输入文件中,所有测试组的 nmn m 之和不超过 2×1052\times10^5,ww 之和也不超过 2×1052\times10^5。答案可能超过 32 位整数范围。

样例

1
3 3 2
2
10 1
42

来源

Codeforces 2000E。题意按原题整理,保留原题署名;测试数据由本站独立构造。