oj.uz

Submission #820149

# Submission time Handle Problem Language Result Execution time Memory
820149 2023-08-10T20:30:05 Z WLZ Quality Of Living (IOI10_quality) C++17
100 / 100
 2566 ms 175584 KB 
#include "quality.h"
#include <bits/stdc++.h>
using namespace std;

int R, C, H, W;
int Q[3001][3001];

bool check(int k) {
  vector< vector<int> > pre(R + 1, vector<int>(C + 1, 0));
  for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) if (Q[i][j] <= k) pre[i + 1][j + 1] = 1;
  for (int i = 1; i <= R; i++) for (int j = 1; j <= C; j++) pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
  for (int i = H; i <= R; i++) {
    for (int j = W; j <= C; j++) {
      if (pre[i][j] - pre[i - H][j] - pre[i][j - W] + pre[i - H][j - W] >= (H * W + 1) / 2) return true;
    }
  }
  return false;
}

int rectangle(int _R, int _C, int _H, int _W, int _Q[3001][3001]) {
  R = _R, C = _C, H = _H, W = _W;
  for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) Q[i][j] = _Q[i][j];

  int lo = 1, hi = R * C;
  while (lo < hi) {
    //cerr << lo << endl;
    int mid = (lo + hi) / 2;
    if (check(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 19 ms 3784 KB Output is correct
8 Correct 19 ms 3772 KB Output is correct
9 Correct 17 ms 3680 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 19 ms 3784 KB Output is correct
8 Correct 19 ms 3772 KB Output is correct
9 Correct 17 ms 3680 KB Output is correct
10 Correct 254 ms 20100 KB Output is correct
11 Correct 247 ms 27076 KB Output is correct
12 Correct 124 ms 17528 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 19 ms 3784 KB Output is correct
8 Correct 19 ms 3772 KB Output is correct
9 Correct 17 ms 3680 KB Output is correct
10 Correct 254 ms 20100 KB Output is correct
11 Correct 247 ms 27076 KB Output is correct
12 Correct 124 ms 17528 KB Output is correct
13 Correct 2512 ms 175584 KB Output is correct
14 Correct 2566 ms 175488 KB Output is correct
15 Correct 2329 ms 165052 KB Output is correct