oj.uz

답안 #338662

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
338662 2020-12-23T15:33:02 Z blue 삶의 질 (IOI10_quality) C++17
100 / 100
 2111 ms 175768 KB 
#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.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 35948 KB Output is correct
2 Correct 33 ms 35948 KB Output is correct
3 Correct 32 ms 35948 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 35948 KB Output is correct
2 Correct 33 ms 35948 KB Output is correct
3 Correct 32 ms 35948 KB Output is correct
4 Correct 34 ms 36588 KB Output is correct
5 Correct 34 ms 36588 KB Output is correct
6 Correct 34 ms 36588 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 35948 KB Output is correct
2 Correct 33 ms 35948 KB Output is correct
3 Correct 32 ms 35948 KB Output is correct
4 Correct 34 ms 36588 KB Output is correct
5 Correct 34 ms 36588 KB Output is correct
6 Correct 34 ms 36588 KB Output is correct
7 Correct 50 ms 38884 KB Output is correct
8 Correct 49 ms 39404 KB Output is correct
9 Correct 49 ms 39276 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 35948 KB Output is correct
2 Correct 33 ms 35948 KB Output is correct
3 Correct 32 ms 35948 KB Output is correct
4 Correct 34 ms 36588 KB Output is correct
5 Correct 34 ms 36588 KB Output is correct
6 Correct 34 ms 36588 KB Output is correct
7 Correct 50 ms 38884 KB Output is correct
8 Correct 49 ms 39404 KB Output is correct
9 Correct 49 ms 39276 KB Output is correct
10 Correct 259 ms 58364 KB Output is correct
11 Correct 242 ms 58348 KB Output is correct
12 Correct 151 ms 50924 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 35948 KB Output is correct
2 Correct 33 ms 35948 KB Output is correct
3 Correct 32 ms 35948 KB Output is correct
4 Correct 34 ms 36588 KB Output is correct
5 Correct 34 ms 36588 KB Output is correct
6 Correct 34 ms 36588 KB Output is correct
7 Correct 50 ms 38884 KB Output is correct
8 Correct 49 ms 39404 KB Output is correct
9 Correct 49 ms 39276 KB Output is correct
10 Correct 259 ms 58364 KB Output is correct
11 Correct 242 ms 58348 KB Output is correct
12 Correct 151 ms 50924 KB Output is correct
13 Correct 2111 ms 175680 KB Output is correct
14 Correct 2065 ms 175768 KB Output is correct
15 Correct 1902 ms 168484 KB Output is correct