Submission #797326

#	Time	Username	Problem	Language	Result	Execution time	Memory
797326		andecaandeci	Quality Of Living (IOI10_quality)	C++17	100 / 100	1383 ms	70968 KiB

quality

#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
int rectangle(int n, int m, int h, int w, int a[3001][3001]) {
  int num=h*w/2+1, pre[n][m];
  int l=1, r=n*m, ans=n*m;
  while(l<=r) {
    int mid=l+r>>1;
    for(int i=0; i<n; i++) {
      for(int j=0; j<m; j++) {
        pre[i][j]=(a[i][j]<=mid);
        if(i) pre[i][j]+=pre[i-1][j];
        if(j) pre[i][j]+=pre[i][j-1];
        if(i && j) pre[i][j]-=pre[i-1][j-1];
      }
    }
    bool can=0;
    for(int i=h-1; i<n; i++) {
      for(int j=w-1; j<m; j++) {
        int sum=pre[i][j];
        if(i-h>=0) sum-=pre[i-h][j];
        if(j-w>=0) sum-=pre[i][j-w];
        if(i-h>=0 && j-w>=0) sum+=pre[i-h][j-w];
        if(sum>=num) {can=1; break;}
      }
      if(can) break;
    }
    if(can) ans=mid, r=mid-1;
    else l=mid+1;
  }
  return ans;
}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:8:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    8 |     int mid=l+r>>1;
      |             ~^~

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