Subtask 1 $(N \leq 50, Q \leq 100)$:

We can keep track of the beauty value of the cow at each position in the grid. After each update, we recompute the attractiveness index for every possible picture, keeping track of the maximum index.

Every update requires spending $O(K^2)$ time computing the attractiveness index for each of $(N - K + 1)^2$ possible pictures. Over $Q$ updates, the total time complexity is $O(QN^2K^2)$.

My C++ code:

#include <algorithm>
#include <ios>
#include <iostream>
#include <vector>

using namespace std;

void solve() {

    int k;
    int n;
    int q;

    cin >> n >> k >> q;

    vector vals(n, vector<int>(n));

    for (int i = 0; i < q; ++i) {
        int c;
        int r;
        cin >> r >> c;
        --r;
        --c;
        cin >> vals[r][c];
        int mx_sum = 0;
        for (int j = 0; j <= n - k; ++j) {
            for (int l = 0; l <= n - k; ++l) {
                int cur_sum = 0;
                for (int m = 0; m < k; ++m) {
                    for (int o = 0; o < k; ++o) {
                        cur_sum += vals[j + m][l + o];
                    }
                }
                mx_sum = max(mx_sum, cur_sum);
            }
        }
        cout << mx_sum << '\n';
    }

}

int main() {

    cin.tie(nullptr);

    ios_base::sync_with_stdio(false);

    solve();

    return 0;

}

Subtask 2 $(N \leq 50)$:

An inefficiency to our solution in Subtask 1 is recomputing the attractiveness index for each picture. In fact, each update will only alter the attractiveness index in up to $K^2$ pictures. A cow at position $(r, c)$ can only belong to the pictures whose top-left corner has row and column in the ranges $[r - K + 1, r]$ and $[c - K + 1, c]$ respectively.

For each of these pictures, the attractiveness index increases by exactly the change in the updated cow’s beauty value. We can maintain the attractiveness index for all $(N - K + 1)^2$ pictures, updating affected pictures after every update.

After each update, scanning every picture allows us to find the maximum attractiveness index in $O(N^2)$, resulting in a total time complexity of $O(QN^2)$.

Full Credit:

Because the problem guarantees that each cow's beauty value only increases, every picture's attractiveness index is non-decreasing. Instead of rescanning all pictures, comparing updated ones against the current maximum suffices.

The time complexity is $O(N^2 + QK^2)$.

My C++ code:

#include <algorithm>
#include <ios>
#include <iostream>
#include <vector>

using namespace std;

void solve() {

    int k;
    int n;
    int q;

    cin >> n >> k >> q;

    int mx_sum = 0;
    vector sums(n, vector<int>(n));
    vector vals(n, vector<int>(n));

    for (int i = 0; i < q; ++i) {
        int c;
        int r;
        int v;
        cin >> r >> c >> v;
        --r;
        --c;
        const int diff = v - vals[r][c];
        vals[r][c] = v;
        for (int j = max(r - k + 1, 0); j <= min(r, n - k); ++j) {
            for (int l = max(c - k + 1, 0); l <= min(c, n - k); ++l) {
                sums[j][l] += diff;
                mx_sum = max(mx_sum, sums[j][l]);
            }
        }
        cout << mx_sum << '\n';
    }

}

int main() {

    cin.tie(nullptr);

    ios_base::sync_with_stdio(false);

    solve();

    return 0;

}