Submission #1175718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175718		nagornz	Quality Of Living (IOI10_quality)	C++20	100 / 100	1456 ms	106440 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>

using namespace std;

int rectangle(int n, int m, int row, int col, int arr[3001][3001]) {
    vector <vector <int>> a(n + 1, vector <int> (m + 1));
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) a[i + 1][j + 1] = arr[i][j];
    int l = 1, r = n * m;
    int ans = r;
    int cnt = row * col / 2 + 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        vector <vector <int>> aa(n + 1, vector <int> (m + 1));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                aa[i][j] = (a[i][j] <= mid);
                aa[i][j] = aa[i][j] + aa[i - 1][j] + aa[i][j - 1] - aa[i - 1][j - 1];
            }
        }
        bool can = false;
        for (int i = row; i <= n; i++) {
            for (int j = col; j <= m; j++) {
                int sum = aa[i][j] - aa[i - row][j] - aa[i][j - col] + aa[i - row][j - col];
                if (sum >= cnt) {
                    can = true;
                    break;
                }
            }
            if (can) break;
        }
        if (can) {
            r = mid - 1;
            ans = min(ans, mid);
        }
        else l = mid + 1;
    }
    return ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20