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 flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
#define sqr(x) (x)*(x)
using namespace std;

int a[1010][1010],h[1010],st[1010],pos[1010],n,ans,area;

void color(int x,int y,int j)
{
    a[x][max(y-j,1)]++; 
    a[x][min(y+j,n)+1]--;
}

int main()
{
    int x,y,r,m;
    cin >> n >> m;
    while (m--)
    {
        cin >> x >> y >> r;
        int j=r-1;
        color(x,y,j);
        for (int i=1;i<r;i++)
        {
            while (j && sqr(2*j-1)+sqr(2*i-1)>sqr(2*r-1)) j--;
            if (x+i<=n) color(x+i,y,j);
            if (x-i>0) color(x-i,y,j);
        }
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++) a[i][j]+=a[i][j-1], area+=a[i][j]>0;
        int last=0;
        a[i][n+1]=1;
        for (int j=1;j<=n+1;j++)
        {
            if (!a[i][j]) h[j]++; 
            else h[j]=0;
            if (!last || h[j]>st[last]) st[++last]=h[j], pos[last]=j;
            else
            {
                while (last && st[last]>=h[j]) ans=max(ans,st[last]*(j-pos[last])), last--;
                st[++last]=h[j];
            }
        }
    }
    cout << ans << " " << area << endl;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
#define sqr(a) ((a) * (a))
const int N = 1010;
using namespace std;
int n, m;
int a[N][N], L[N], R[N], b[N];

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    int x, y, Radius;
    FOR(j, 0, m) {
        cin >> x >> y >> Radius;
        Radius = min(Radius, n + n);
        int rr = sqr(2 * Radius - 1);
        FOR(i, max(1, x - Radius + 1), min(n + 1, x + Radius)) {
            if (i == x) {
                a[i][max(1, y - Radius + 1)]++;
                a[i][min(n + 1, y + Radius)]--;
            }
            else  {
                int h = abs(i - x) - 1; h = sqr(2 * h + 1);
                int l = y, r = n, k = n;
                while (l <= r) {
                    int mid = l + r >> 1;
                    if (sqr(2 * (mid - y) + 1) + h > rr) {
                        k = mid; r = mid - 1;
                    }
                    else
                        l = mid + 1;
                }
                a[i][k + 1]--;
                l = 1, r = y, k = 1;
                while (l <= r) {
                    int mid = l + r >> 1;
                    if (sqr(2 * (y - mid) + 1) + h > rr) {
                        k = mid; l = mid + 1;
                    }
                    else
                        r = mid - 1;
                }
                a[i][k]++;
            }
        }
    }
    int ans = 0, area = 0;
    REP(i, 1, n) REP(j, 1, n) {
        a[i][j] += a[i][j - 1];
        if (a[i][j]) area++;
    }
    REP(i, 1, n) {
        REP(j, 1, n) if (a[i][j]) b[j] = 0; else b[j]++;
        //REP(j, 1, n) cout << a[i][j] << ' '; cout << endl;
        L[1] = 0;
        REP(j, 2, n) {
            int k = j - 1;
            while (k && b[k] >= b[j]) k = L[k];
            L[j] = k;
        }
        R[n] = n + 1;
        REPD(j, n - 1, 1) {
            int k = j + 1;
            while (k <= n && b[k] >= b[j]) k = R[k];
            R[j] = k;
        }
        REP(j, 1, n)
            ans = max(ans, (R[j] - L[j] - 1) * b[j]);
    }
    cout << ans << ' ' << area;
    return 0;
}

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
const int BUFSIZE = (1<<12) + 17;
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp && !REACHEOF) { \
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);
const int MN = 1011;

int a[MN][MN], h[MN], all, res;
int m, n, st[MN], l[MN], r[MN];

int solve() {
    int top = 0; st[0] = 0;
    FOR(i,1,n) {
        while (top && h[st[top]] >= h[i]) --top;
        l[i] = st[top] + 1;
        st[++top] = i;
    }
    top = 0; st[top] = n+1;
    FORD(i,n,1) {
        while (top && h[st[top]] >= h[i]) --top;
        r[i] = st[top] - 1;
        st[++top] = i;
    }

    // DEBUG(row);
    // PR(h[row], n);
    // PR(l, n);
    // PR(r, n);

    FOR(i,1,n)
        res = max(res, h[i] * (r[i] - l[i] + 1));
}

int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        int x, y, r; scanf("%d%d%d", &x, &y, &r);
        double rr = (r - 0.5) * (r - 0.5);
        FOR(i,max(1,x-r+1),min(n,x+r-1)) {
            double dx = abs(x - i) - 0.5;
            double dy = sqrt(rr - dx*dx);

            double y1 = y - 0.5 - dy, y2 = y - 0.5 + dy;

            int l = (int) (floor(y1) + 1e-6) + 1;
            int r = (int) (ceil(y2) + 1e-6);
            if (l < 1) l = 1; if (r > n+1) r = n+1;

            a[i][l]++; a[i][r+1]--;
        }
    }

    FOR(i,1,n) {
        FOR(j,1,n) a[i][j] = a[i][j-1] + a[i][j];
    }

    res = 0;
    FOR(i,1,n) {
        FOR(j,1,n) {
            if (a[i][j]) ++all, h[j] = 0;
            else h[j]++;
        }
        solve();
    }

    printf("%d %d\n", res, all);
    return 0;
}

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00000001
#define oo 1111111111
#define mod 1000000007
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, x) memset(a, x, sizeof(a))
//#include <conio.h>
//#define g 9.81
#define maxn 1005
#define maxm 105
double const PI=4*atan(1.0);

const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

#define eps 1e-6

void OPEN(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
}

int a[maxn][maxn], n, m;
double x[maxm], y[maxm], r[maxm];

int main(){    
  //  OPEN();
    scanf("%d %d", &n, &m);
    FOR(i, 1, m) {
        scanf("%lf %lf %lf", &x[i], &y[i], &r[i]);
        x[i] -= 0.5;
        y[i] -= 0.5;
        r[i] -= 0.5;
    }
    MS(a, 0);
    FOR(i, 1, n){
        vector<pair<int, int> > V;
        FOR(j, 1, m){

            int low, high;
            if(abs(i - x[j] - 0.5) < eps){
                low = max(1, int(y[j] - r[j] + ep) + 1);
                high = min(n, int(y[j] + r[j] + ep));
                V.PB(MP(low, high));
            }

            else if(i < x[j]){
                if(r[j] > abs(x[j] - i) + eps){
                    double d = sqrt(r[j] * r[j] - (x[j] - i) * (x[j] - i) - ep);
                    int low = max(1, int(y[j] - d) + 1);
                    int high = min(n, int(y[j] + d) + 1);
                    V.PB(MP(low, high));
                }
            }

            else{
                if(r[j] > abs(x[j] - i + 1) + eps){
                    double d = sqrt(r[j] * r[j] - (x[j] - i + 1) * (x[j] - i + 1) - ep);
                    int low = max(1, int(y[j] - d) + 1);
                    int high = min(n, int(y[j] + d) + 1);
                    V.PB(MP(low, high));
                  //  cout << low << "  "<< high << endl;
                }            
            }
        }
        sort(V.begin(), V.end());
       // cout << V.size() << endl;
        int run = 0;
        rep(j, V.size()){
            run = max(run, V[j].fi);
            while(run <= V[j].se){
                a[run][i] = 1;
                run++;
            }
        }
    }
    /* 
    FOR(i, 1, n){
        FOR(j, 1, n) printf("%d",a[i][j]); printf("\n");
    }
    */
    int h[maxn], l[maxn], r[maxn], res = 0, num = 0;
    MS(h, 0);
    FOR(i, 1, n){
        FOR(j, 1, n){
            if(a[i][j]){
                h[j] = 0;
                num++;
            }
            else h[j]++;
        }

        h[0] = -1; h[n + 1] = -1;
        l[1] = 1;
        FOR(j, 2, n){
            l[j] = j;
            while(h[l[j] - 1] >= h[j]) l[j] = l[l[j] - 1];
        }

        r[n] = n;
        FORD(j, n - 1, 1){
            r[j] = j;
            while(h[r[j] + 1] >= h[j]) r[j] = r[r[j] + 1];
        }

        FOR(j, 2, n){
            res = max(res, h[j] *(r[j] - l[j] + 1));
        }

    }
    printf("%d %d", res, num);

}

Code mẫu của skyvn97

#include<stdio.h>
#include<math.h>
#define MAX   1111
int a[MAX][MAX];
int h[MAX][MAX];
int l[MAX];
int r[MAX];
int st[MAX];
int size,sr,sm;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int sx[]={1,1,-1,-1};
int sy[]={1,-1,1,-1};
int m,n;
bool inside(int x,int y) {
    if (x<1) return (false);
    if (x>n) return (false);
    if (y<1) return (false);
    if (y>n) return (false);
    return (true);
}
bool filled(int cx,int cy,int r,int x,int y) {
    return ((2*cx-2*x-1)*(2*cx-2*x-1)+(2*cy-2*y-1)*(2*cy-2*y-1)<=(2*r-1)*(2*r-1));
}
void init(void) {
    int i,j,k,l;
    int x,y,r;
    scanf("%d",&n);
    scanf("%d",&m);
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&x);
        scanf("%d",&y);
        scanf("%d",&r);
        a[x][y]=1;
        for (j=1;j<r;j=j+1)
            for (k=0;k<4;k=k+1)
                if (inside(x+j*dx[k],y+j*dy[k])) a[x+j*dx[k]][y+j*dy[k]]=1;
        for (j=1;j<r;j=j+1)
            for (k=1;k<r;k=k+1) {
                if (filled(x,y,r,x-j,y-k)) {
                    for (l=0;l<4;l=l+1)
                        if (inside(x-j*sx[l],y-k*sy[l])) a[x-j*sx[l]][y-k*sy[l]]=1;
                }
                else break;
            }
    }
    sr=0;   
    for (i=1;i<=n;i=i+1)
        for (j=1;j<=n;j=j+1) {                  
            if (a[i][j]==0) h[i][j]=h[i-1][j]+1;
            else {          
                h[i][j]=0;
                sr++;
            }           
        }                   
}
void process(void) {
    sm=0;
    int i,j;
    for (i=1;i<=n;i=i+1) {
        size=0;
        l[1]=1;
        for (j=2;j<=n;j=j+1) {
            if (h[i][j]>h[i][j-1]) {
                l[j]=j;
                size++;
                st[size]=j-1;
            }
            else {
                while ((size>0) && (h[i][st[size]]>=h[i][j])) size--;
                if (size==0) l[j]=1;
                else l[j]=st[size]+1;
            }
        }
        size=0;
        r[n]=n;
        for (j=n-1;j>=1;j=j-1) {
            if (h[i][j]>h[i][j+1]) {
                r[j]=j;
                size++;
                st[size]=j+1;
            }           
            else {
                while ((size>0) && (h[i][st[size]]>=h[i][j])) size--;
                if (size==0) r[j]=n;
                else r[j]=st[size]-1;
            }
        }   
        for (j=1;j<=n;j=j+1)
            if (sm<h[i][j]*(r[j]-l[j]+1)) sm=h[i][j]*(r[j]-l[j]+1);
    }
    printf("%d %d",sm,sr);
}
int main(void) {
    init();
    process();
    return 0;
}