Submission #1264025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264025		DeltaStruct	Quality Of Living (IOI10_quality)	C++20	100 / 100	857 ms	71020 KiB

quality

#include <bits/stdc++.h>
using namespace std;

int rectangle(int h,int w,int x,int y,int A[3001][3001]){
  vector B(h+1,vector<int>(w+1));
  int l(h*w),r(0),mid;
  while(abs(r-l)>1){
    mid = (l+r)/2;
    for (int i(0);i < h;++i) for (int k(0);k < w;++k) B[i+1][k+1] = B[i+1][k]+B[i][k+1]-B[i][k]+(A[i][k]>mid);
    bool f = 0;
    for (int i(x);i <= h;++i) for (int k(y);k <= w;++k) f |= (B[i][k]-B[i-x][k]-B[i][k-y]+B[i-x][k-y]<=x*y/2);
    if (f) l = mid;
    else r = mid;
  }
  return l;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20