Tree Investment

[Link] https://www.acmicpc.net/problem/16235

Each year runs in a fixed order: spring, summer, autumn, then winter. In spring, trees in each cell are processed from youngest to oldest. A tree consumes food equal to its age and then grows by one. If the cell cannot feed a tree, that tree and every older tree still waiting in that cell die; processing stops there. In summer, each dead tree returns floor(age / 2) food to its cell. Autumn trees whose age is a multiple of five produce one age-one tree in each of the eight neighboring cells that are inside the farm. Finally, winter adds the scheduled food to every cell.

Each cell stores tree ages in a sorted vector, youngest first. Spring scans from the front. As soon as food is insufficient, the current tree and all unprocessed (older) trees are dead; sum their food return from the back and shrink the vector to keep only survivors. This avoids erasing from the middle while preserving the correct death rule. Autumn offspring are counted in a separate grid so that newborns do not reproduce in the same autumn. They are inserted at the front, preserving age order for next spring.

There are at most N * N cells and K <= 1000 years (N <= 10). Let T_y be the number of living trees entering year y. Each year visits O(N^2) cells and processes each tree a constant number of times, including at most eight neighbor checks per reproducing tree. Newborns are collected per cell and inserted into each sorted vector in one batch; because each reproducing tree creates at most eight newborns, total insertion work is also bounded by the number of trees processed that year. The running time is O(N^2*K + sum_y T_y) and storage is O(N^2 + T_max). Tree counts can grow rapidly, so complexity cannot be bounded by N, M, and K alone without accounting for population size.

C++17

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, years;
    cin >> n >> m >> years;

    vector<vector<int>> winterFood(n, vector<int>(n));
    for (auto& row : winterFood) {
        for (int& food : row) cin >> food;
    }

    vector<vector<int>> food(n, vector<int>(n, 5));
    vector<vector<vector<int>>> trees(n, vector<vector<int>>(n));
    for (int i = 0; i < m; ++i) {
        int row, column, age;
        cin >> row >> column >> age;
        trees[--row][--column].push_back(age);
    }
    for (auto& row : trees) {
        for (auto& cell : row) sort(cell.begin(), cell.end());
    }

    constexpr int dr[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
    constexpr int dc[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
    vector<vector<int>> deadFood(n, vector<int>(n));

    for (int year = 0; year < years; ++year) {
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                auto& cell = trees[r][c];
                int alive = 0;
                deadFood[r][c] = 0;
                while (alive < static_cast<int>(cell.size()) &&
                       food[r][c] >= cell[alive]) {
                    food[r][c] -= cell[alive];
                    ++cell[alive];
                    ++alive;
                }
                for (int i = static_cast<int>(cell.size()) - 1; i >= alive; --i) {
                    deadFood[r][c] += cell[i] / 2;
                }
                cell.resize(alive);
            }
        }

        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) food[r][c] += deadFood[r][c];
        }

        vector<vector<int>> offspring(n, vector<int>(n));
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                for (int age : trees[r][c]) {
                    if (age % 5 != 0) continue;
                    for (int d = 0; d < 8; ++d) {
                        const int nr = r + dr[d];
                        const int nc = c + dc[d];
                        if (0 <= nr && nr < n && 0 <= nc && nc < n) {
                            ++offspring[nr][nc];
                        }
                    }
                }
            }
        }
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                trees[r][c].insert(trees[r][c].begin(), offspring[r][c], 1);
                food[r][c] += winterFood[r][c];
            }
        }
    }

    int answer = 0;
    for (const auto& row : trees) {
        for (const auto& cell : row) answer += cell.size();
    }
    cout << answer << '\n';
    return 0;
}