Submission #331281

#	Time	Username	Problem	Language	Result	Execution time	Memory
331281		joseacaz	Quality Of Living (IOI10_quality)	C++17	100 / 100	2483 ms	140424 KiB

quality

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

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int MAXN = 3005;
int pre[MAXN][MAXN];

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

int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
    int s = 1, e = R*C, mid, val, ans = 1;
    while(s <= e)
    {
        mid = (s + e) / 2;
        
        for(int i = 0; i < R; i++)
            for(int j = 0; j < C; j++)
                pre[i + 1][j + 1] = (Q[i][j] <= mid);
        
        for(int i = 1; i <= R; i++)
            for(int j = 1; j <= C; j++)
                pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
        
        val = 0;
        for(int i = H; i <= R; i++)
            for(int j = W; j <= C; j++)
                if(sum(i - H + 1, j - W + 1, i, j) > H*W/2)
                    val = 1;
        
        if(val)
        {
            ans = mid;
            e = mid - 1;
        }
        else
            s = mid + 1;
    }

    return ans;
}

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