Cod sursa(job #3227248)

Utilizator dariadragomir23Dragomir Daria dariadragomir23 Data 28 aprilie 2024 18:48:56
Problema Plantatie Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <cmath>
 
using namespace std;
 
ifstream fin("plantatie.in");
ofstream fout("plantatie.out");

long long rmq[10][501][501];
 
int main()
{
    long long n, q;
    fin >> n >> q;
    for(long long i = 1; i <= n; i++)
        for(long long j = 1; j <= n; j++)
            fin >> rmq[0][i][j];
    for(long long p = 1; p <= 9; p++){
        for(long long i = 1; i <= n; i++){
            for(long long j = 1; j <= n; j++){
                long long lat = (1 << (p - 1));
                rmq[p][i][j] = max(
                    max( rmq[p - 1][i - lat][j], rmq[p - 1][i][j - lat]),
                    max( rmq[p - 1][i][j], rmq[p - 1][i - lat][j - lat])
                );
            }
        }
    }
 
    while(q--){
        long long l, c, k;
        fin >> l >> c >> k;
        l += (k - 1);
        c += (k - 1);
        long long lat2 = log2(k), lat3 = (1 << lat2);
        fout << max(
            max( rmq[lat2][l - k + lat3][c - k + lat3], rmq[lat2][l - k + lat3][c]),
            max( rmq[lat2][l][c - k + lat3], rmq[lat2][l][c])
        ) << '\n';
    }
    return 0;
}