USACO 5.3 Big Barn

Similar dynamic programming problem as the previous Home On The Range.

#include <vector>
#include <iostream>
#include <fstream>
#include <climits>

using namespace std;
int N, T;
vector<vector<int>> dp;

int main() {
    ifstream fin("bigbrn.in");
    ofstream fout("bigbrn.out");
    
    fin >> N >> T;
    dp = vector<vector<int>>(N, vector<int>(N, 1));
    int x, y;
    for (int i = 0; i < T; ++i) {
        fin >> x >> y;
        dp[x - 1][y - 1] = 0;
    }
    
    int ans = INT_MIN;
    for (int i = N - 2; i >= 0; --i) {
        for (int j = N - 2; j >= 0; --j) {
            if (!dp[i][j]) continue;
            dp[i][j] = std::min(std::min(dp[i + 1][j], dp[i][j + 1]),
                                dp[i + 1][j + 1]) + 1;
            ans = std::max(dp[i][j], ans);
        }
    }
    
    cout << ans << endl;
    fout << ans << endl;
}