Arhiva de probleme 	Marime 	1.12 kb
Raporteaza aceasta sursa

#include <fstream>

using namespace std;

ifstream fin ("plantatie.in");
ofstream fout ("plantatie.out");

const int Dim = 501;
int D[Dim][Dim][10],n,m,k,A[Dim][Dim],log2[Dim];
void DynamicRMQ() ;
int Query(int i, int j, int k);

int main() {
	
	 for(int i = 2; i < Dim; ++i)
        log2[i] = log2[i / 2] + 1;
	fin >> n >> m;
	for ( int i = 1; i <= n; ++i)
		for ( int j = 1; j <= n; ++j)
			fin >> A[i][j];
	DynamicRMQ();
	int x,y,k;
	for ( ; m > 0; --m) {
		fin >> x >> y >> k;
		fout << Query(x,y,k) << "\n";
	}
}

 
void DynamicRMQ() {
	
	for ( int i = 1; i <= n; ++i)
		for ( int j = 1; j <= n; ++j)
			D[i][j][0] = A[i][j];
	for ( int k = 1; ( 1 << k ) <= n; ++k) {
		int next = 1 << ( k - 1);
		for ( int i = 1; i + ( 1 << (k - 1) ) <= n; ++i)
			for ( int j = 1; j + ( 1 << ( k - 1) )  <= n; ++j)
					D[i][j][k] = max(D[i][j][k-1], max(D[i][j + next][k - 1],
					max(D[i + next][j][k - 1] , D[i + next][j + next][k - 1])));  
				}
}

int Query(int i, int j, int k) {
	
	int log = log2[k];
	return max(D[i][j][log], max(D[i][j +k - (1 << log)][log], max(D[i+k  - (1 << log)][j][log], D[i+k  - (1 << log)][j+k -(1 << log) ][log])));
}