自动搬运

查看原文

来自洛谷，原作者为

	Log_x **

搬运于2025-08-24 21:44:25，当前版本为作者最后更新于2017-08-07 15:45:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

• 一道比较裸的模拟……

• 首先我们考虑枚举子三角形的顶点（当然顶点既可能在子三角形的最上方，也可能在最下方），然后枚举子三角形的边长，计算子三角形中每一层数的和。

• 这里每一层数的和可以预处理其前缀和，然后在枚举中 $O(1)$ 得到，那么总的时间复杂度大概也就是 $O(n^2k)$。而且实际上我们一旦发现枚举的子三角形超出了大三角形的边界就可以直接结束枚举边长的循环，这样也能快很多。

• 不过题目中对三角边边长不能超过 $2k$ 的要求是没有必要的（这好像是译者自己加进去的……），因为这是可以通过其它条件推出来的，具体为什么也可以看看我的博客，这里就不多论述了。

Code

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long ll;
const int N = 705;
ll Ans = -1e15, a[N][N];
int n, d;

inline void CkMax(ll &x, const ll &y) {if (x < y) x = y;}

inline int get()
{
    char ch; int res = 0; bool f = false;
    while (((ch = getchar()) < '0' || ch > '9') && ch != '-');
    if (ch == '-') f = true;
     else res = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9')
     res = (res << 3) + (res << 1) + ch - '0';
    return f ? -res : res;
}

inline void put(ll x)
{
    if (x < 0) 
     x = -x, putchar('-');
    if (x > 9) put(x / 10);
    putchar(x % 10 + 48);
}

int main()
{
    n = get(); d = get();
    for (int i = 1; i <= n; ++i)
     for (int j = 1; j <= i; ++j)
      a[i][j] = a[i][j - 1] + get();
    ll res, num;
    for (int i = 1; i <= n; ++i)
     for (int j = 1; j <= i; ++j)
     {
         res = num = 0ll;
         for (int k = 1; k <= (d << 1); ++k)
         {
             int tx = i + k - 1, ty = j + k - 1;
             if (tx > n || ty > tx) break;
             res += a[tx][ty] - a[tx][j - 1]; num += k;
            if (k >= d) CkMax(Ans, res / num);
        }
        res = num = 0ll;
        for (int k = 1; k <= (d << 1); ++k)
        {
            int tx = i - k + 1, ty = j - k + 1;
            if (tx < 1 || ty < 1 || j > tx) break;
            res += a[tx][j] - a[tx][ty - 1]; num += k;
            if (k >= d) CkMax(Ans, res / num);
        }
     }
    return put(Ans), 0;
}