Submission #252309

#	Time	Username	Problem	Language	Result	Execution time	Memory
252309		SamAnd	Quality Of Living (IOI10_quality)	C++17	100 / 100	2964 ms	175624 KiB

quality

//#include "quality.h"
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 3003;

int n, m, h, w;
int a[N][N];

int p[N][N];
bool stg(int x)
{
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
            if (a[i][j] <= x)
                ++p[i][j];
        }
    }
    for (int x2 = h; x2 <= n; ++x2)
    {
        for (int y2 = w; y2 <= m; ++y2)
        {
            int x1 = x2 - h;
            int y1_ = y2 - w;
            int q = p[x2][y2] - p[x2][y1_] - p[x1][y2] + p[x1][y1_];
            if (q >= h * w / 2 + 1)
                return true;
        }
    }
    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
    n = R;
    m = C;
    h = H;
    w = W;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            a[i][j] = Q[i - 1][j - 1];
        }
    }

    int l = 1, r = n * m;
    int ans;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (stg(m))
        {
            ans = m;
            r = m - 1;
        }
        else
            l = m + 1;
    }
    return ans;
}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:63:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ans;
            ^~~

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