oj.uz

Submission #481832

# Submission time Handle Problem Language Result Execution time Memory
481832 2021-10-22T02:38:35 Z theshadow_04 Quality Of Living (IOI10_quality) C++17
100 / 100
 1668 ms 142044 KB 
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3005;

int r, c, h, w, p[maxn][maxn];
int small[maxn][maxn], big[maxn][maxn];

int Get1(int x, int y, int u, int v) {
  return small[u][v] - small[u][y - 1] - small[x - 1][v] + small[x - 1][y - 1];
}

int Get2(int x, int y, int u, int v) {
  return big[u][v] - big[u][y - 1] - big[x - 1][v] + big[x - 1][y - 1];
}

bool Check(int x) {
  for(int i = 1; i <= r; ++ i) {
    for(int j = 1; j <= c; ++ j) {
      small[i][j] = small[i - 1][j] + small[i][j - 1] - small[i - 1][j - 1] + (p[i][j] < x);
      big[i][j] = big[i - 1][j] + big[i][j - 1] - big[i - 1][j - 1] + (p[i][j] > x);
    }
  }
  for(int i = h; i <= r; ++ i) {
    for(int j = w; j <= c; ++ j) {
      int cur1 = Get1(i - h + 1, j - w + 1, i, j);
      int cur2 = Get2(i - h + 1, j - w + 1, i, j);
      if(cur1 >= cur2) return 1;
    }
  }
  return 0;
}

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 = 1; i <= r; ++ i) {
    for(int j = 1; j <= c; ++ j) p[i][j] = Q[i - 1][j - 1];
  }
  int Le = h * w / 2, Ri = r * c + 1;
  while(Ri - Le > 1) {
    int mid = (Le + Ri) >> 1;
    if(Check(mid)) Ri = mid;
    else Le = mid;
  }
  return Ri;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 2 ms 2124 KB Output is correct
5 Correct 2 ms 1996 KB Output is correct
6 Correct 2 ms 2124 KB Output is correct
7 Correct 18 ms 6988 KB Output is correct
8 Correct 18 ms 6964 KB Output is correct
9 Correct 22 ms 6868 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 2 ms 2124 KB Output is correct
5 Correct 2 ms 1996 KB Output is correct
6 Correct 2 ms 2124 KB Output is correct
7 Correct 18 ms 6988 KB Output is correct
8 Correct 18 ms 6964 KB Output is correct
9 Correct 22 ms 6868 KB Output is correct
10 Correct 187 ms 36492 KB Output is correct
11 Correct 172 ms 36480 KB Output is correct
12 Correct 112 ms 27448 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 2 ms 2124 KB Output is correct
5 Correct 2 ms 1996 KB Output is correct
6 Correct 2 ms 2124 KB Output is correct
7 Correct 18 ms 6988 KB Output is correct
8 Correct 18 ms 6964 KB Output is correct
9 Correct 22 ms 6868 KB Output is correct
10 Correct 187 ms 36492 KB Output is correct
11 Correct 172 ms 36480 KB Output is correct
12 Correct 112 ms 27448 KB Output is correct
13 Correct 1668 ms 141920 KB Output is correct
14 Correct 1604 ms 142044 KB Output is correct
15 Correct 1456 ms 141928 KB Output is correct