CSP/前缀和/前缀和.cpp

#include <iostream>
#include <math.h>
#include <cstring>
using namespace std;
int x[3001][3001];
long long int F[3001][3001];
long long int line[3001];
/*
一维index表示行数，二维index表示列数


*/
int main()
{
    int n, m, p;
    cin >> n >> m >> p;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            if (i == 0 || j == 0)
                x[i][j] = 0;
            else
                cin >> x[i][j];
            if (j == 0 && i == 0)
                F[i][j] = x[i][j];
            else if (i == 0)
                F[i][j] = F[i][j - 1] + x[i][j];
            else if (j == 0)
            {
                line[j] = x[i][j];
                F[i][j] = F[i - 1][j] + line[j];
            }
            else
            {
                line[j] = line[j - 1] + x[i][j];
                F[i][j] = F[i - 1][j] + line[j];
            }
        }
        memset(line, 0, sizeof(line));
    }
    // for (int i = 0; i <= n; i++)
    // {
    //     for (int j = 0; j <= m; j++)
    //     {
    //         cout << F[i][j] << "       ";
    //     }
    //     cout << endl;
    // }
    long long int max = 0;
    int r_out = 1, c_out = 1;
    for (int r = 1; r <= n; r++)
    {
        for (int c = 1; c <= m; c++)
        {
            int r_up = (r - p - 1 >= 0) ? r - p - 1 : 0;
            int r_down = (r + p <= n) ? r + p : n - 1;
            int c_left = (c - p - 1 >= 0) ? c - p - 1 : 0;
            int c_right = (c + p <= m) ? c + p : m - 1;
            long long int m = F[r_down][c_right] - F[r_down][c_left] - F[r_up][c_right] + F[r_up][c_left];
            // cout << r << "  " << c << " " << m << endl;
            if (m > max)
            {
                max = m;
                r_out = r;
                c_out = c;
            }
        }
    }
    cout << max << endl;
    cout << r_out << " " << c_out;
    return 0;
}