IOI camp 2017. C

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define mp make_pair
#define pb push_back

constexpr int N = (int)1e6 + 111;
constexpr int md = (int)1e9+7;
constexpr int INF = (int)2e9;
constexpr int inv6 = 175000002;
constexpr double eps = 1e-7;
constexpr double LOG2_3 = log2((double)3);

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

void add(int& a,int b){
    a = (a + b >= md ? a + b - md : a + b);
}

class myInt{
public:
    int cnt2, cnt3;
    bool is_negative, is_zero;
    bool lessZero() const{
        return is_negative && !is_zero;
    }
    bool lessEqualZero() const{
        return is_negative || is_zero;
    }
    bool biggerZero() const{
        return !is_negative && !is_zero;
    }
    bool biggerEqualZero() const{
        return !is_negative || is_zero;
    }
public:
    myInt():cnt2(0),cnt3(0),is_negative(false),is_zero(false){
        cnt3 = 502;
        is_negative = true;
    }
    myInt(int x):cnt2(0),cnt3(0),is_negative(false),is_zero(false){
        if(x == 0)
            is_zero = true;
        else if(x < 0)
            is_negative = true;
        x = abs(x);
        while(x > 0 && x % 2 == 0) x /= 2, cnt2++;
        while(x > 0 && x % 3 == 0) x /= 3, cnt3++;
    }
    myInt(const myInt& other){
        this->cnt2 = other.cnt2;
        this->cnt3 = other.cnt3;
        this->is_negative = other.is_negative;
        this->is_zero = other.is_zero;
    }
    myInt& operator=(const myInt& other){
        this->cnt2 = other.cnt2;
        this->cnt3 = other.cnt3;
        this->is_negative = other.is_negative;
        this->is_zero = other.is_zero;
        return *this;
    }
    friend
    bool operator<(const myInt& a,const myInt& b){
        if(a.is_zero && b.is_zero)
            return false;
        if(a.is_zero || b.is_zero){
            if(a.is_zero)
                return b.biggerZero();
            if(b.is_zero)
                return a.lessZero();
        }
        if(a.lessZero() && b.biggerEqualZero())
            return true;
        if(a.lessEqualZero() && b.biggerZero())
            return true;
        if(a.biggerEqualZero() && b.lessEqualZero())
            return false;
        if(a.lessEqualZero() && b.lessEqualZero()){
            return (a.cnt2-b.cnt2) - (b.cnt3 - a.cnt3) * LOG2_3 > eps;
        } else {
            return (a.cnt2-b.cnt2) - (b.cnt3 - a.cnt3) * LOG2_3 < eps;
        }
    }
    friend
    myInt operator*(const myInt& a,const myInt& b){
        myInt result = a;
        result.cnt2 += b.cnt2;
        result.cnt3 += b.cnt3;
        result.is_negative ^= b.is_negative;
        result.is_zero |= b.is_zero;
        if(result.is_zero){
            result.is_zero = true;
            result.cnt2 = result.cnt3 = 0;
            result.is_negative = false;
        }
        return result;
    }
    friend
    istream& operator>>(istream& o,myInt& x){
        int value;
        o >> value;
        x = myInt(value);
        return o;
    }
    int getValue() const{
        if(is_zero) return 0;
        int x = 1;
        for(int i = 0; i < cnt2; i++) x = (1ll * x * 2) % md;
        for(int i = 0; i < cnt3; i++) x = (1ll * x * 3) % md;
        if(is_negative) x = md - x;
        return x;
    }
};

myInt a[501][501];
myInt dp[2][501][501];
myInt st[2][11][501];
int n,m,k;

myInt getMin(int l,int r){
    l = max(1,l);
    r = min(m,r);
    int j = __lg(r - l + 1);
    return min(st[1][j][l],st[1][j][r-(1<<j)+1]);
}

myInt getMax(int l,int r){
    l = max(1,l);
    r = min(m,r);
    int j = __lg(r - l + 1);
    return max(st[0][j][l],st[0][j][r-(1<<j)+1]);
}

void solve(int test){
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
    for(int t = 0; t < 2; t++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                dp[t][i][j] = myInt();
                dp[t][i][j].is_negative = !t;
            }
        }
    }

    for(int i = 1; i <= m; i++){
        dp[0][1][i] = dp[1][1][i] = a[1][i];
    }

    for(int i = 2; i <= n; i++){
        for(int j = 1; j <= m; j++){
            st[0][0][j] = dp[0][i-1][j];
            st[1][0][j] = dp[1][i-1][j];
        }
        for(int t = 1; t < 11; t++){
            for(int j = 1; j + (1 << t) - 1 <= m; j++){
                st[0][t][j] = max(st[0][t-1][j],st[0][t-1][j+(1<<(t-1))]);
                st[1][t][j] = min(st[1][t-1][j],st[1][t-1][j+(1<<(t-1))]);
            }
        }
        for(int j = 1; j <= m; j++){
            myInt maxVal = getMax(j-k,j+k);
            myInt minVal = getMin(j-k,j+k);
            if(dp[0][i][j] < maxVal * a[i][j]) dp[0][i][j] = maxVal * a[i][j];
            if(dp[0][i][j] < minVal * a[i][j]) dp[0][i][j] = minVal * a[i][j];
            if(maxVal * a[i][j] < dp[1][i][j]) dp[1][i][j] = maxVal * a[i][j];
            if(minVal * a[i][j] < dp[1][i][j]) dp[1][i][j] = minVal * a[i][j];
        }
    }
    cout << max_element(&dp[0][n][1],&dp[0][n][m+1])->getValue() << "\n";
    return;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tests = 1;
    cin >> tests;
    for(int test = 1; test <= tests; test++){
        solve(test);
    }
    return 0;
}
/**
**/