USACO 2026 First Contest Bronze Division - Photoshoot

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The idea is to keep track of the beauty of each individual cell, and also the beauty of every possible \(K \times K\) photo area. We don’t recompute everything from scratch after each update, instead we only update the photo areas that are actually affected by the changed cell. Since (N) is at most about 500, directly storing a grid of size \((N-K+1) \times (N-K+1)\) for the square sums is totally fine.

Whenever a query changes the value of cell \((r, c)\), we find how much the beauty changed and then add that difference to every \(K \times K\) square that contains that cell. A cell \((r, c)\) belongs to squares whose top-left corners are in ranges \([r-K+1, r]\) and \([c-K+1, c]\), clamped so they stay inside the grid. We update those squares, adjust their stored sum, and while doing that we also track the maximum value among all squares, which is our answer after each query.

Since one update only affects at most \(K^2\) squares and \(K \le N\), this runs fast enough for the constraints. Everything starts at zero and we just apply changes as queries come in, printing the current maximum beauty after each one.

Source code

The source code for the solution in C++ can be seen below.

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

using namespace std;

long long square_sums[506][506];
long long beauty[506][506];

void solve() {
    int N, K, Q;
    cin >> N >> K;

    cin >> Q;
    long long globalMax = 0;

    while (Q--) {
        int r, c;
        long long v;
        cin >> r >> c >> v;

        long long db = v - beauty[r][c];
        beauty[r][c] = v;

        int r_start = max(1, r - K + 1);
        int r_end = min(r, N - K + 1);
        int c_start = max(1, c - K + 1);
        int c_end = min(c, N - K + 1);

        for (int i = r_start; i <= r_end; ++i) {
            for (int j = c_start; j <= c_end; ++j) {
                square_sums[i][j] += db;
                if (square_sums[i][j] > globalMax) {
                    globalMax = square_sums[i][j];
                }
            }
        }

        cout << globalMax << "\n";
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}