Submission #482088

#	Time	Username	Problem	Language	Result	Execution time	Memory
482088		kiennguyen246	Quality Of Living (IOI10_quality)	C++14	0 / 100	1 ms	716 KiB

quality

/**
 * \author Nguyen Duc Kien
 * \date ./10/2021
 */

///-------------------------------------------///

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3005;

int m, n, h, w, a[maxn][maxn], b[maxn][maxn], s[maxn][maxn];

int Sum(int x1, int y1, int x2, int y2)
{
    return (s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
}

bool ok(int x)
{
//        memset(s, 0, sizeof(s));
    for (int i = 1; i <= m; i ++)
        for (int j = 1; j <= n; j ++)
        {
            b[i][j] = (a[i][j] >= x ? 1 : -1);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + b[i][j];
        }
    for (int i = 1; i + h - 1 <= m; i ++)
        for (int j = 1; j + w - 1 <= n; j ++)
            if (Sum(i, j, i + h - 1, j + w - 1) > 0) return 1;
    return 0;

}

int rectangle(int __m, int __n, int __h, int __w, int __a[3001][3001])
{
    m = __m, n = __n, h = __h, w = __h;
    for (int i = 1; i <= m; i ++) for (int j = 1; j <= n; j ++) a[i][j] = __a[i][j];
    int l = 1, r = m * n + 5;
//        ok(20);
    while (r - l > 1)
    {
        int mid = (l + r) / 2;
        if (ok(mid)) l = mid;
        else r = mid;
    }
    return l;

}

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