# Untitled

unknown
c_cpp
a month ago
1.6 kB
2
Indexable
Never
```#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
int R, C;
cin >> R >> C;

vector<vector<int>> grid(R, vector<int>(C));
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
cin >> grid[i][j];
}
}

// DP table to store the minimum heights needed
vector<vector<int>> dp(R, vector<int>(C, 0));

// Initialize the dp table with the initial heights
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
dp[i][j] = grid[i][j];
}
}

// Iterate through the grid to adjust heights
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
if (i > 0) {
dp[i][j] = max(dp[i][j], dp[i-1][j] - 1);
}
if (j > 0) {
dp[i][j] = max(dp[i][j], dp[i][j-1] - 1);
}
}
}

// Iterate through the grid in reverse order to ensure the height differences
for (int i = R - 1; i >= 0; --i) {
for (int j = C - 1; j >= 0; --j) {
if (i < R - 1) {
dp[i][j] = max(dp[i][j], dp[i+1][j] - 1);
}
if (j < C - 1) {
dp[i][j] = max(dp[i][j], dp[i][j+1] - 1);
}
}
}

// Calculate the total number of boxes added