oj.uz

Submission #390175

# Submission time Handle Problem Language Result Execution time Memory
390175 2021-04-15T13:47:25 Z MilosMilutinovic Quality Of Living (IOI10_quality) C++14
100 / 100
 3467 ms 175372 KB 
/**
 *    author:  milos
 *    created: 15.04.2021 12:47:15       
**/
#include <bits/stdc++.h>
#include "quality.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 InRect = [&](int x1, int x2, int y1, int y2, int x, int y) {
    return x1 <= x && x <= x2 && y1 <= y && y <= y2; 
  };
  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 x = -1, y = -1;
    for (int i = 0; i < R; i++) {
      for (int j = 0; j < C; j++) {
        if (Q[i][j] == val) {
          x = i; y = j;
        }
      }
    }
    assert(x != -1 && y != -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 >= P / 2 + 1) {
          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:61:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int mid = bot + top >> 1;
      |               ~~~~^~~~~
quality.cpp:17:8: warning: variable 'InRect' set but not used [-Wunused-but-set-variable]
   17 |   auto InRect = [&](int x1, int x2, int y1, int y2, int x, int y) {
      |        ^~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 844 KB Output is correct
5 Correct 4 ms 832 KB Output is correct
6 Correct 4 ms 844 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 844 KB Output is correct
5 Correct 4 ms 832 KB Output is correct
6 Correct 4 ms 844 KB Output is correct
7 Correct 34 ms 3132 KB Output is correct
8 Correct 29 ms 3180 KB Output is correct
9 Correct 25 ms 2956 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 844 KB Output is correct
5 Correct 4 ms 832 KB Output is correct
6 Correct 4 ms 844 KB Output is correct
7 Correct 34 ms 3132 KB Output is correct
8 Correct 29 ms 3180 KB Output is correct
9 Correct 25 ms 2956 KB Output is correct
10 Correct 354 ms 22844 KB Output is correct
11 Correct 341 ms 22888 KB Output is correct
12 Correct 171 ms 13520 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 844 KB Output is correct
5 Correct 4 ms 832 KB Output is correct
6 Correct 4 ms 844 KB Output is correct
7 Correct 34 ms 3132 KB Output is correct
8 Correct 29 ms 3180 KB Output is correct
9 Correct 25 ms 2956 KB Output is correct
10 Correct 354 ms 22844 KB Output is correct
11 Correct 341 ms 22888 KB Output is correct
12 Correct 171 ms 13520 KB Output is correct
13 Correct 3467 ms 175372 KB Output is correct
14 Correct 3454 ms 175180 KB Output is correct
15 Correct 3143 ms 161148 KB Output is correct