oj.uz

Submission #335588

# Submission time Handle Problem Language Result Execution time Memory
335588 2020-12-13T08:47:36 Z Joshc Quality Of Living (IOI10_quality) C++
100 / 100
 2544 ms 96096 KB 
#include <cstdio>
#include <algorithm>
using namespace std;

int r, c, h, w, prefix[3001][3001];

void update(int i, int j, int delta) {
  prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + delta;
}

int query(int x1, int y1, int x2, int y2) {
  return prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1];
}

bool work(int x, int grid[3001][3001], int r, int c, int h, int w) {
  for (int i=0; i<=r; i++) {
    prefix[i][0] = 0;
  }
  for (int j=0; j<=c; j++) {
    prefix[0][j] = 0;
  }
  for (int i=1; i<=r; i++) {
    for (int j=1; j<=c; j++) {
      if (grid[i-1][j-1]>x) {
        update(i, j, -1);
      } else if (grid[i-1][j-1]==x) {
        update(i, j, 0);
      } else {
        update(i, j, 1);
      }
    }
  }
  for (int i=1; i<=r-h+1; i++) {
    for (int j=1; j<=c-w+1; j++) {
      if (query(i, j, i+h-1, j+w-1) >= 0) return true;
    }
  }
  return false;
}

int rectangle(int r, int c, int h, int w, int grid[3001][3001]) {
  int low=1, high=r*c, mid;
  while (low != high) {
    mid = (low+high)>>1;
    if (!work(mid, grid, r, c, h, w)) {
      low = mid+1;
    } else {
      high = mid;
    }
  }
  return low;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 3 ms 1260 KB Output is correct
5 Correct 3 ms 1260 KB Output is correct
6 Correct 3 ms 1260 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 3 ms 1260 KB Output is correct
5 Correct 3 ms 1260 KB Output is correct
6 Correct 3 ms 1260 KB Output is correct
7 Correct 22 ms 3920 KB Output is correct
8 Correct 22 ms 3948 KB Output is correct
9 Correct 20 ms 3820 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 3 ms 1260 KB Output is correct
5 Correct 3 ms 1260 KB Output is correct
6 Correct 3 ms 1260 KB Output is correct
7 Correct 22 ms 3920 KB Output is correct
8 Correct 22 ms 3948 KB Output is correct
9 Correct 20 ms 3820 KB Output is correct
10 Correct 310 ms 23020 KB Output is correct
11 Correct 257 ms 22892 KB Output is correct
12 Correct 138 ms 15724 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 3 ms 1260 KB Output is correct
5 Correct 3 ms 1260 KB Output is correct
6 Correct 3 ms 1260 KB Output is correct
7 Correct 22 ms 3920 KB Output is correct
8 Correct 22 ms 3948 KB Output is correct
9 Correct 20 ms 3820 KB Output is correct
10 Correct 310 ms 23020 KB Output is correct
11 Correct 257 ms 22892 KB Output is correct
12 Correct 138 ms 15724 KB Output is correct
13 Correct 2544 ms 85984 KB Output is correct
14 Correct 2511 ms 96096 KB Output is correct
15 Correct 2355 ms 93360 KB Output is correct