Submission #224424

#	Time	Username	Problem	Language	Result	Execution time	Memory
224424		jhnah917	Quality Of Living (IOI10_quality)	C++14	100 / 100	3434 ms	176496 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
using namespace std;

int n, m, h, w;
int a[3030][3030];
int v[3030][3030]; //x 이상이면 1, 미만이면 0

void make(int x){
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
        if(a[i][j] > x) v[i][j] = 1;
        else if(a[i][j] < x) v[i][j] = -1;
        else v[i][j] = 0;
    }
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
        v[i][j] += v[i-1][j];
        v[i][j] += v[i][j-1];
        v[i][j] -= v[i-1][j-1];
    }
}

int query(int x, int xx, int y, int yy){
    return v[xx][yy] - v[x-1][yy] - v[xx][y-1] + v[x-1][y-1];
}

int chk(int x){
    make(x);
    for(int i=1; i<=n; i++) if(i+h-1 <= n){
        for(int j=1; j<=m; j++) if(j+w-1 <= m){
            if(query(i, i+h-1, j, j+w-1) <= 0) return 1;
        }
    }
    return 0;
}

int rectangle(int N, int M, int H, int W, int A[3001][3001]) {
    n = N, m = M, h = H, w = W;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) a[i][j] = A[i-1][j-1];
    int l = 0, r = 3030*3030;
    while(l < r){
        int m = l + r >> 1;
        if(chk(m)) r = m;
        else l = m + 1;
    }
    return r;
}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l + r >> 1;
                 ~~^~~

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