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

F. Photoshoot for Gorillas

  • 传统题
  • 2000ms
  • 256MiB

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。题意按原题整理,保留原题署名;测试数据由本站独立构造。

前缀和与差分

未参加
状态
已结束
规则
XCPC
题目
6
开始于
2026-10-28 18:00
结束于
2026-10-28 23:00
持续时间
5 小时
主持人
参赛人数
17