oj.uz

Submission #512140

# Submission time Handle Problem Language Result Execution time Memory
512140 2022-01-16T06:59:53 Z 600Mihnea Quality Of Living (IOI10_quality) C++17
100 / 100
 1992 ms 139980 KB 
#include "quality.h"
#include <bits/stdc++.h>

using namespace std;

int a[3001][3001];

int getsum(int r1, int c1, int r2, int c2) {
  return a[r2][c2] - a[r1 - 1][c2] - a[r2][c1 - 1] + a[r1 - 1][c1 - 1];
}

int rectangle(int n, int m, int h, int w, int matrix[3001][3001]) {
  /// for the example the solution is 9

  int low = 1, high = n * m, sol = -1;
  while (low <= high) {
    int want = (low + high) / 2;
    bool ok = 0;
    for (int i = 1; i <= n; i++) {
      int current = 0;
      for (int j = 1; j <= m; j++) {
        if (matrix[i - 1][j - 1] > want) {
          a[i][j] = -1;
        } else {
          if (matrix[i - 1][j - 1] < want) {
            a[i][j] = +1;
          } else {
            a[i][j] = 0;
          }
        }
        current += a[i][j];
        a[i][j] = a[i - 1][j] + current;
      }
    }
    for (int i = 1; i + h - 1 <= n; i++) {
      for (int j = 1; j + w - 1 <= m; j++) {
        if (getsum(i, j, i + h - 1, j + w - 1) >= 0) {
          ok = 1;
        }
      }
    }
    if (ok) {
      sol = want;
      high = want - 1;
    } else {
      low = want + 1;
    }
  }
  assert(sol != -1);
  return sol;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 552 KB Output is correct
2 Correct 0 ms 552 KB Output is correct
3 Correct 1 ms 552 KB Output is correct
4 Correct 2 ms 1212 KB Output is correct
5 Correct 2 ms 1212 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 18 ms 3916 KB Output is correct
8 Correct 17 ms 3912 KB Output is correct
9 Correct 16 ms 3780 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 552 KB Output is correct
2 Correct 0 ms 552 KB Output is correct
3 Correct 1 ms 552 KB Output is correct
4 Correct 2 ms 1212 KB Output is correct
5 Correct 2 ms 1212 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 18 ms 3916 KB Output is correct
8 Correct 17 ms 3912 KB Output is correct
9 Correct 16 ms 3780 KB Output is correct
10 Correct 218 ms 22852 KB Output is correct
11 Correct 229 ms 22856 KB Output is correct
12 Correct 106 ms 15432 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 552 KB Output is correct
2 Correct 0 ms 552 KB Output is correct
3 Correct 1 ms 552 KB Output is correct
4 Correct 2 ms 1212 KB Output is correct
5 Correct 2 ms 1212 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 18 ms 3916 KB Output is correct
8 Correct 17 ms 3912 KB Output is correct
9 Correct 16 ms 3780 KB Output is correct
10 Correct 218 ms 22852 KB Output is correct
11 Correct 229 ms 22856 KB Output is correct
12 Correct 106 ms 15432 KB Output is correct
13 Correct 1944 ms 139976 KB Output is correct
14 Correct 1992 ms 139980 KB Output is correct
15 Correct 1869 ms 133080 KB Output is correct