oj.uz

Submission #597622

# Submission time Handle Problem Language Result Execution time Memory
597622 2022-07-16T12:18:04 Z computerbox Quality Of Living (IOI10_quality) C++14
100 / 100
 2323 ms 180852 KB 
#include <bits/stdc++.h>

using namespace std;

vector<vector<int> >precompute(int n, int m, vector<vector<int> >&massiv)
{
  vector<vector<int> >preff(n + 1, vector<int>(m + 1));
  for(int i = 0; i < n; i++)
  {
    for(int j = 0; j < m; j++)
    {
      preff[i + 1][j + 1] = preff[i][j + 1] + preff[i + 1][j] + massiv[i][j] - preff[i][j];
    }
  }
  return preff;
}


int query(int lx, int ly, int rx, int ry, vector<vector<int> >&preff)
{
  return preff[rx][ry] - preff[rx][ly - 1] - preff[lx - 1][ry] + preff[lx - 1][ly - 1];
}


int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	vector<vector<int> >prefsum(R + 1, vector<int>(C + 1));

  int l = 1;
  int r = R * C;
  vector<vector<int> >tmp;
  for(int i = 0; i < R; i++)
  {
    vector<int>row;
    for(int j = 0; j < C; j++)
    {
      row.push_back(Q[i][j]);
    }
    tmp.push_back(row);
  }
  int ans = R * C;
  while(l <= r)
  {
    int mid = l + (r - l) / 2;

    int lim = H * W / 2 + 1;

    vector<vector<int> >tmp1 = tmp;
    for(int i = 0; i < R; i++)
    {
      for(int j = 0; j < C; j++)
      {
        if(tmp1[i][j] > mid)tmp1[i][j] = 0;
        else tmp1[i][j] = 1;
      }
    }

    vector<vector<int> >preff = precompute(R, C, tmp1);

    int sig = 0;
    int maxx = 0;
    for(int i = 0; i < R; i++)
    {
      for(int j = 0; j < C; j++)
      {
        if(i + H - 1 < R  && j + W - 1 < C)
        {
          int sum = query(i + 1, j + 1, i + H, j + W, preff);
          maxx = max(maxx, sum);
          if(sum == lim)
          {
            sig = 1;
            break;
          }

        }
      }
      if(sig)break;
    }

   if(sig){ans = min(ans, mid); r = mid - 1;}
   else if(maxx > lim) r = mid - 1;
   else l = mid + 1;
  }
  return ans;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 444 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 956 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 444 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 956 KB Output is correct
7 Correct 17 ms 3848 KB Output is correct
8 Correct 16 ms 3828 KB Output is correct
9 Correct 15 ms 3632 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 444 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 956 KB Output is correct
7 Correct 17 ms 3848 KB Output is correct
8 Correct 16 ms 3828 KB Output is correct
9 Correct 15 ms 3632 KB Output is correct
10 Correct 248 ms 30892 KB Output is correct
11 Correct 207 ms 30876 KB Output is correct
12 Correct 103 ms 17592 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 444 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 956 KB Output is correct
7 Correct 17 ms 3848 KB Output is correct
8 Correct 16 ms 3828 KB Output is correct
9 Correct 15 ms 3632 KB Output is correct
10 Correct 248 ms 30892 KB Output is correct
11 Correct 207 ms 30876 KB Output is correct
12 Correct 103 ms 17592 KB Output is correct
13 Correct 2323 ms 180852 KB Output is correct
14 Correct 2209 ms 180792 KB Output is correct
15 Correct 1955 ms 166040 KB Output is correct