Weekly-Contest-403

class Solution {
public:
    double minimumAverage(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n =nums.size();
        int ans=(nums[0]+nums[n-1]);
        for(int i =0,j=n-1;i<j;i++,j--){
            ans=min(ans,(nums[i]+nums[j]));
        }
        return ans/2.0;
    }
};

class Solution {
public:
    int minimumArea(vector<vector<int>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
    
        int rows = grid.size();
        int cols = grid[0].size();
        
        int min_row = rows, max_row = -1;
        int min_col = cols, max_col = -1;
        
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == 1) {
                    min_row = min(min_row, r);
                    max_row = max(max_row, r);
                    min_col = min(min_col, c);
                    max_col = max(max_col, c);
                }
            }
        }
        
        if (min_row == rows || max_row == -1) return 0;
        
        int height = max_row - min_row + 1;
        int width = max_col - min_col + 1;
        
        return height * width;
    }
};

class Solution {
public:
    long long maximumTotalCost(vector<int>& nums) {
        int n = nums.size();
        vector<array<long long, 2>> f(n+1);
        for(int i=n-1;i>=0;i--){
            f[i][0]=f[i+1][1]+nums[i];
            f[i][1]=max(f[i+1][1]+nums[i],f[i+1][0]-nums[i]);
        }
        return f[0][0];
    }
};

class Solution {
    vector<vector<int>> rotate(vector<vector<int>>& a) {
        int m = a.size();
        int n = a[0].size();
        vector<vector<int>> b(n, vector<int>(m));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                b[j][m - 1 - i] = a[i][j];
            }
        }
        return b;
    }

    int minimumArea(vector<vector<int>>& a, int u, int d, int l, int r) {
        int left = a[0].size(), right = 0, top = a.size(), bottom = 0;
        for (int i = u; i < d; i++) {
            for (int j = l; j < r; j++) {
                if (a[i][j] == 1) {
                    left = min(left, j);
                    right = max(right, j);
                    top = min(top, i);
                    bottom = i;
                }
            }
        }
        return (right - left + 1) * (bottom - top + 1);
    }

    int f(vector<vector<int>>& a) {
        int ans = INT_MAX;
        int m = a.size();
        int n = a[0].size();
        if (m >= 3) {
            for (int i = 1; i < m; i++) {
                for (int j = i + 1; j < m; j++) {
                    // 图片上左
                    int area = minimumArea(a, 0, i, 0, n);
                    area += minimumArea(a, i, j, 0, n);
                    area += minimumArea(a, j, m, 0, n);
                    ans = min(ans, area);
                }
            }
        }
        if (m >= 2 && n >= 2) {
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    // 图片上中
                    int area = minimumArea(a, 0, i, 0, n);
                    area += minimumArea(a, i, m, 0, j);
                    area += minimumArea(a, i, m, j, n);
                    ans = min(ans, area);
                    // 图片上右
                    area = minimumArea(a, 0, i, 0, j);
                    area += minimumArea(a, 0, i, j, n);
                    area += minimumArea(a, i, m, 0, n);
                    ans = min(ans, area);
                }
            }
        }
        return ans;
    }

public:
    int minimumSum(vector<vector<int>>& grid) {
        auto g = rotate(grid);
        return min(f(grid), f(g));
    }
};