oj.uz

Submission #990456

# Submission time Handle Problem Language Result Execution time Memory
990456 2024-05-30T13:01:31 Z aaaaaarroz Quality Of Living (IOI10_quality) C++17
100 / 100
 971 ms 210908 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 46 ms 108404 KB Output is correct
2 Correct 45 ms 108508 KB Output is correct
3 Correct 46 ms 108540 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 108404 KB Output is correct
2 Correct 45 ms 108508 KB Output is correct
3 Correct 46 ms 108540 KB Output is correct
4 Correct 46 ms 108624 KB Output is correct
5 Correct 47 ms 108632 KB Output is correct
6 Correct 46 ms 108624 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 108404 KB Output is correct
2 Correct 45 ms 108508 KB Output is correct
3 Correct 46 ms 108540 KB Output is correct
4 Correct 46 ms 108624 KB Output is correct
5 Correct 47 ms 108632 KB Output is correct
6 Correct 46 ms 108624 KB Output is correct
7 Correct 53 ms 111188 KB Output is correct
8 Correct 54 ms 111180 KB Output is correct
9 Correct 65 ms 110932 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 108404 KB Output is correct
2 Correct 45 ms 108508 KB Output is correct
3 Correct 46 ms 108540 KB Output is correct
4 Correct 46 ms 108624 KB Output is correct
5 Correct 47 ms 108632 KB Output is correct
6 Correct 46 ms 108624 KB Output is correct
7 Correct 53 ms 111188 KB Output is correct
8 Correct 54 ms 111180 KB Output is correct
9 Correct 65 ms 110932 KB Output is correct
10 Correct 148 ms 125524 KB Output is correct
11 Correct 141 ms 125528 KB Output is correct
12 Correct 93 ms 122196 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 108404 KB Output is correct
2 Correct 45 ms 108508 KB Output is correct
3 Correct 46 ms 108540 KB Output is correct
4 Correct 46 ms 108624 KB Output is correct
5 Correct 47 ms 108632 KB Output is correct
6 Correct 46 ms 108624 KB Output is correct
7 Correct 53 ms 111188 KB Output is correct
8 Correct 54 ms 111180 KB Output is correct
9 Correct 65 ms 110932 KB Output is correct
10 Correct 148 ms 125524 KB Output is correct
11 Correct 141 ms 125528 KB Output is correct
12 Correct 93 ms 122196 KB Output is correct
13 Correct 971 ms 210756 KB Output is correct
14 Correct 968 ms 210908 KB Output is correct
15 Correct 930 ms 203860 KB Output is correct