oj.uz

답안 #390171

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
390171 2021-04-15T13:37:56 Z MilosMilutinovic 삶의 질 (IOI10_quality) C++14
0 / 100
 1 ms 332 KB 
/**
 *    author:  milos
 *    created: 15.04.2021 12:47:15       
**/
#include "quality.h"
#include <bits/stdc++.h>

using namespace std;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
  vector<int> xs;
  for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      xs.push_back(Q[i][j]);
    }
  }
  auto Can = [&](int val) {
    int sum[R][C];
    for (int i = 0; i < R; i++) {
      for (int j = 0; j < C; j++) {
        sum[i][j] = (Q[i][j] <= val ? 1 : 0);
        if (i > 0) sum[i][j] += sum[i - 1][j];
        if (j > 0) sum[i][j] += sum[i][j - 1];
        if (i > 0 && j > 0) sum[i][j] -= sum[i - 1][j - 1];
      }
    }
    int P = H * W;
    for (int i = 0; i < R; i++) {
      for (int j = 0; j < C; j++) {
        int ii = i + H - 1, jj = j + W - 1;
        if (ii >= R || jj >= C) {
          continue;  
        }
        int cnt = sum[ii][jj];
        if (i > 0) cnt -= sum[i - 1][jj];
        if (j > 0) cnt -= sum[ii][j - 1];
        if (i > 0 && j > 0) cnt += sum[i - 1][j - 1];
        if (cnt - 1 == P - cnt) {
          return true;
        }
      }
    }
    return false;
  };
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  int bot = 0, top = (int) xs.size() - 1, ans = 1e9;
  while (bot <= top) {
    int mid = bot + top >> 1;
    if (Can(xs[mid])) {
      ans = xs[mid];
      top = mid - 1;
    } else {
      bot = mid + 1;
    }
  }
  return ans;
}

Compilation message

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:49:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     int mid = bot + top >> 1;
      |               ~~~~^~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -