【題解】ZeroJudge b118: TOI2008 5. 彩色區塊

#include <bits/stdc++.h>
using namespace std;

int n, g[1005][1005][3], cnt[1005][1005];
map <tuple<int, int, int>, int> mp;

int f(int x, int y, int t){
    return (g[x][y][t]-1)/cnt[x][y]+1;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n){
        memset(g, 0, sizeof(g));
        memset(cnt, 0, sizeof(cnt));
        mp.clear();
        for (int iter = 0, l, d, r, u, R, G, B; iter < n; iter++){
            cin >> l >> d >> r >> u >> R >> G >> B;
            if (l > r) swap(l, r);
            if (d > u) swap(d, u);
            cnt[l][d]++;
            cnt[l][u]--;
            cnt[r][d]--;
            cnt[r][u]++;

            g[l][d][0] += R;
            g[l][u][0] -= R;
            g[r][d][0] -= R;
            g[r][u][0] += R;

            g[l][d][1] += G;
            g[l][u][1] -= G;
            g[r][d][1] -= G;
            g[r][u][1] += G;

            g[l][d][2] += B;
            g[l][u][2] -= B;
            g[r][d][2] -= B;
            g[r][u][2] += B;
        }
        for (int i = 0; i < 1000; i++){
            for (int j = 0; j < 1000; j++){
                if (i > 0){
                    cnt[i][j] += cnt[i-1][j];
                    for (int k = 0; k < 3; k++){
                        g[i][j][k] += g[i-1][j][k];
                    }
                }
                if (j > 0){
                    cnt[i][j] += cnt[i][j-1];
                    for (int k = 0; k < 3; k++){
                        g[i][j][k] += g[i][j-1][k];
                    }
                }
                if (i > 0 && j > 0){
                    cnt[i][j] -= cnt[i-1][j-1];
                    for (int k = 0; k < 3; k++){
                        g[i][j][k] -= g[i-1][j-1][k];
                    }
                }
                if (!cnt[i][j]) continue;
                mp[{f(i,j,0), f(i,j,1), f(i,j,2)}]++;
            }
        }
        tuple <int, int, int> ans;
        int mx = 0;
        for (auto i:mp){
            if (i.second > mx){
                mx = i.second;
                ans = i.first;
            }
        }
        cout << get<0>(ans) << " " << get<1>(ans) << " " << get<2>(ans) << "\n";
    }
}