oj.uz

Submission #950877

# Submission time Handle Problem Language Result Execution time Memory
950877 2024-03-20T21:04:48 Z Yell0 Quality Of Living (IOI10_quality) C++17
100 / 100
 1440 ms 140476 KB 
#include <bits/stdc++.h>

using namespace std;
const int MN=3001;
int pfs[MN][MN], q[MN][MN];

int qry(int r1, int c1, int r2, int c2) {
  int ans = pfs[r2][c2];
  if(r1 > 0) ans -= pfs[r1-1][c2];
  if(c1 > 0) ans -= pfs[r2][c1-1];
  if(r1 > 0 && c1 > 0) ans += pfs[r1-1][c1-1];
  return ans;
}

int rectangle(int R, int C, int H, int W, int Q[MN][MN]) {

  int l = 1, h = R*C, target = H*W/2, ans;
  while(l <= h) {
    int X = (l+h)/2;

    bool chk = 0;
    for(int r=0; r<R; ++r) {
      for(int c=0; c<C; ++c) {
        pfs[r][c] = Q[r][c] <= X;
        if(r > 0) pfs[r][c] += pfs[r-1][c];
        if(c > 0) pfs[r][c] += pfs[r][c-1];
        if(r > 0 && c > 0) pfs[r][c] -= pfs[r-1][c-1];
      }
    }
    for(int r=0; r+H-1<R; ++r) {
      for(int c=0; c+W-1<C; ++c) {
        if(qry(r, c, r+H-1, c+W-1) > target) {
          chk = 1;
        }
      }
    }

    if(chk) {
      h = X-1;
      ans = X;
    } else l = X+1;
  }
  return ans;
}

Compilation message

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:43:10: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |   return ans;
      |          ^~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 13 ms 9052 KB Output is correct
8 Correct 12 ms 9052 KB Output is correct
9 Correct 12 ms 9048 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 13 ms 9052 KB Output is correct
8 Correct 12 ms 9052 KB Output is correct
9 Correct 12 ms 9048 KB Output is correct
10 Correct 150 ms 31672 KB Output is correct
11 Correct 134 ms 31756 KB Output is correct
12 Correct 79 ms 28712 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 13 ms 9052 KB Output is correct
8 Correct 12 ms 9052 KB Output is correct
9 Correct 12 ms 9048 KB Output is correct
10 Correct 150 ms 31672 KB Output is correct
11 Correct 134 ms 31756 KB Output is correct
12 Correct 79 ms 28712 KB Output is correct
13 Correct 1440 ms 140476 KB Output is correct
14 Correct 1335 ms 140476 KB Output is correct
15 Correct 1292 ms 133340 KB Output is correct