Untitled

mail@pastecode.io avatar
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
    int total_boxes_added = 0;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            total_boxes_added += (dp[i][j] - grid[i][j]);
        }
    }
    
    cout << total_boxes_added << endl;
    
    return 0;
}
Leave a Comment