oj.uz

Submission #958115

# Submission time Handle Problem Language Result Execution time Memory
958115 2024-04-05T00:20:33 Z hyakup Quality Of Living (IOI10_quality) C++17
100 / 100
 1319 ms 141724 KB 
#include <bits/stdc++.h>
#include "quality.h"
using namespace std;

const int maxn = 3e3 + 1;
vector<vector<int>> v( maxn, vector<int>(maxn)), s1( maxn, vector<int>(maxn)), s2( maxn, vector<int>(maxn));

bool check( int n, int m, int h, int w, int k ){
  for( int i = 1; i <= n; i++ ) for( int j = 1; j <= m; j++ ){
    s1[i][j] = ((v[i][j] < k) ? 1 : 0 ) + s1[i - 1][j] + s1[i][j - 1] - s1[i - 1][j - 1];
    if( i >= h && j >= w ){
      int v1 = s1[i][j] - s1[i - h][j] - s1[i][j - w] + s1[i - h][j - w];
      if( v1 >= (h*w + 1)/2 ) return true;
    }
  }
  return false;
}

int bs( int n, int m, int h, int w ){
  int l = 1, r = n*m;
  while( l < r ){
    int mid = ( l + r )/2;
    if( check(n, m, h, w, mid) ) r = mid;
    else l = mid + 1;
  }
  return r - 1;
}

int rectangle( int n, int m, int h, int w, int q[maxn][maxn] ){
  for( int i = 1; i <= n; i++ ) for( int j = 1; j <= m; j++ ) v[i][j] = q[i - 1][j - 1];
  return bs(n, m, h, w);
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 108628 KB Output is correct
2 Correct 47 ms 108524 KB Output is correct
3 Correct 48 ms 108368 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 108628 KB Output is correct
2 Correct 47 ms 108524 KB Output is correct
3 Correct 48 ms 108368 KB Output is correct
4 Correct 49 ms 108372 KB Output is correct
5 Correct 48 ms 108372 KB Output is correct
6 Correct 50 ms 108376 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 108628 KB Output is correct
2 Correct 47 ms 108524 KB Output is correct
3 Correct 48 ms 108368 KB Output is correct
4 Correct 49 ms 108372 KB Output is correct
5 Correct 48 ms 108372 KB Output is correct
6 Correct 50 ms 108376 KB Output is correct
7 Correct 56 ms 110680 KB Output is correct
8 Correct 58 ms 110416 KB Output is correct
9 Correct 68 ms 110440 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 108628 KB Output is correct
2 Correct 47 ms 108524 KB Output is correct
3 Correct 48 ms 108368 KB Output is correct
4 Correct 49 ms 108372 KB Output is correct
5 Correct 48 ms 108372 KB Output is correct
6 Correct 50 ms 108376 KB Output is correct
7 Correct 56 ms 110680 KB Output is correct
8 Correct 58 ms 110416 KB Output is correct
9 Correct 68 ms 110440 KB Output is correct
10 Correct 172 ms 118864 KB Output is correct
11 Correct 172 ms 118912 KB Output is correct
12 Correct 102 ms 118868 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 108628 KB Output is correct
2 Correct 47 ms 108524 KB Output is correct
3 Correct 48 ms 108368 KB Output is correct
4 Correct 49 ms 108372 KB Output is correct
5 Correct 48 ms 108372 KB Output is correct
6 Correct 50 ms 108376 KB Output is correct
7 Correct 56 ms 110680 KB Output is correct
8 Correct 58 ms 110416 KB Output is correct
9 Correct 68 ms 110440 KB Output is correct
10 Correct 172 ms 118864 KB Output is correct
11 Correct 172 ms 118912 KB Output is correct
12 Correct 102 ms 118868 KB Output is correct
13 Correct 1278 ms 141724 KB Output is correct
14 Correct 1319 ms 141724 KB Output is correct
15 Correct 1213 ms 141536 KB Output is correct