oj.uz

Submission #908639

# Submission time Handle Problem Language Result Execution time Memory
908639 2024-01-16T15:42:11 Z andro Quality Of Living (IOI10_quality) C++14
100 / 100
 2304 ms 177560 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 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 2 ms 2712 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 2 ms 2712 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 19 ms 5836 KB Output is correct
8 Correct 18 ms 5844 KB Output is correct
9 Correct 17 ms 5844 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 2 ms 2712 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 19 ms 5836 KB Output is correct
8 Correct 18 ms 5844 KB Output is correct
9 Correct 17 ms 5844 KB Output is correct
10 Correct 232 ms 27320 KB Output is correct
11 Correct 222 ms 27380 KB Output is correct
12 Correct 114 ms 20016 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 2 ms 2712 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 19 ms 5836 KB Output is correct
8 Correct 18 ms 5844 KB Output is correct
9 Correct 17 ms 5844 KB Output is correct
10 Correct 232 ms 27320 KB Output is correct
11 Correct 222 ms 27380 KB Output is correct
12 Correct 114 ms 20016 KB Output is correct
13 Correct 2299 ms 176008 KB Output is correct
14 Correct 2304 ms 177560 KB Output is correct
15 Correct 2134 ms 160880 KB Output is correct