Submission #338662

#	Time	Username	Problem	Language	Result	Execution time	Memory
338662		blue	Quality Of Living (IOI10_quality)	C++17	100 / 100	2111 ms	175768 KiB

quality

#include "quality.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int grid[3001][3001];

int R, C, H, W;
int** Q;

int b_search(int a, int b)
{
    if(a == b) return a;
    int m = (a+b)/2;

    for(int i = 0; i <= R; i++) grid[i][0] = 0;
    for(int j = 0; j <= C; j++) grid[0][j] = 0;

    for(int i = 1; i <= R; i++)
    {
        for(int j = 1; j <= C; j++)
        {
            grid[i][j] = (Q[i-1][j-1] <= m);
            grid[i][j] += grid[i-1][j];
            grid[i][j] += grid[i][j-1];
            grid[i][j] -= grid[i-1][j-1];
        }
    }

    for(int i = H; i <= R; i++)
    {
        for(int j = W; j <= C; j++)
        {
            if(2*(grid[i][j] - grid[i-H][j] - grid[i][j-W] + grid[i-H][j-W]) >= H*W)
            {
                return b_search(a, m);
            }
        }
    }

    return b_search(m+1, b);
}

int rectangle(int r, int c, int h, int w, int q[3001][3001])
{
    R = r;
    C = c;
    H = h;
    W = w;

    Q = new int*[3001];
    for(int i = 0; i <= 3000; i++)
    {
        Q[i] = new int[3000];
        for(int j = 0; j <= 3000; j++) Q[i][j] = q[i][j];
    }

    return b_search(0, R*C-1);
}

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