p168.cpp
======================
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

vector<vector<short>> solve(int N, int M, const vector<vector<short>>& A) {
    vector<vector<short>> Q(
        M, vector<short>(N + M, numeric_limits<short>::max())
    );

    for(int x = 0; x < N; x++) {
        for(int y = 0; y < M; y++) {
            Q[y][x + y] = A[x][y];
        }
    }

    for(int i = M - 1; i >= 0; i--) {
        for(int j = N + M - 1; j >= 0; j--) {
            short curr = Q[i][j];
            short down =
                (i + 1 < M) ? Q[i + 1][j] : numeric_limits<short>::max();
            short right =
                (j + 1 < N + M) ? Q[i][j + 1] : numeric_limits<short>::max();
            Q[i][j] = min({curr, down, right});
        }
    }

    vector<vector<short>> B(N, vector<short>(M));
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            B[i][j] = Q[j][i + j];
        }
    }

    return B;
}

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

    int N, M;
    cin >> N >> M;

    vector<vector<short>> A(N, vector<short>(M));
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> A[i][j];
        }
    }

    vector<vector<short>> B = solve(N, M, A);

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cout << B[i][j] << (j == M - 1 ? '\n' : ' ');
        }
    }

    return 0;
}

=================
statement.txt
======================
168. Matrix
time limit per test: 0.5 sec.
memory limit per test: 16000 KB
input: standard
output: standard



You are given N*M matrix A. You are to find such matrix B, that B[i,j]=min{ A[x,y] : (y>=j) and (x>=i+j-y) }

Input
On the first line of the input there are two integer numbers, N and M (1<=N,M<=1000). Then matrix A follows: next N lines contains M integers each (not greater than 32000 by absolute value). The j-th number on then i-th of this lines is A[i,j].

Output
Write matrix B in the same format as matrix A, but without N and M.

Sample test(s)

Input
3 3
1 2 3
4 5 6
7 8 9

Output
1 2 3
2 3 6
3 6 9
Author:	NNSU #2 team
Resource:	
Date:	








=================
