Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 1010;
const int lim = 1005;
using namespace std;

int a[N][N], L[N], R[N], H[N], pp[lim];
bool P[lim];
int n, m, np;

inline bool ok(int &x) {
    int x2 = round(sqrt(x));
    if (x2 * x2 == x) return true;
    int l = 1, r = np, mid;
    while (l <= r) {
        mid = l + r >> 1;
        if (pp[mid] == x) return true;
        if (pp[mid] < x) l = mid + 1; else r = mid - 1;
    }
    return false;
}

int main() {
    ios :: sync_with_stdio(0); cin.tie();
    cin >> n >> m;
    int i, j;
    for(i = 2; i <= sqrt(lim); i++)
    if (!P[i]) {
        for(j = i * i; j < lim; j += i)
            P[j] = true;
    }
    for(i = 2; i < lim; i++)
        if (!P[i]) pp[++np] = i * i * i;
    int row, l, r, k, res = 0;
    for(i = 1; i <= m; i++) {
        cin >> row >> l >> r >> k;
        a[row][l] += k; a[row][r + 1] -= k;
    }
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            a[i][j] += a[i][j - 1];
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++)
            if (ok(a[i][j])) H[j]++; else H[j] = 0;
        L[1] = 0;
        for(j = 2; j <= n; j++) {
            for(k = j - 1; k > 0 && H[k] >= H[j]; k = L[k]) ;
            L[j] = k;
        }
        R[n] = n + 1;
        for(j = n - 1; j; j--) {
            for(k = j + 1; k <= n && H[k] >= H[j]; k = R[k]) ;
            R[j] = k;
        }
        for(j = 1; j <= n; j++)
            res = max(res, H[j] * (R[j] - L[j] - 1));
    }
    cout << res;
    return 0;
}