Submission #597622

#	Time	Username	Problem	Language	Result	Execution time	Memory
597622		computerbox	Quality Of Living (IOI10_quality)	C++14	100 / 100	2323 ms	180852 KiB

quality

#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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20