Submission #996180

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
996180	2024-06-10 08:31:28	Yazan_SA	Quality Of Living (IOI10_quality)	C++14	100 / 100	979 ms	105720 KiB

quality

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
  vector<vector<int>>v(3001,vector<int>(3001));
  int l=1,r=R*C,bs;
  while(l<r){
    bs=(l+r)/2;
    bool is=0;
    for(int i=1; i<=R; i++)for(int j=1; j<=C; j++)
        v[i][j]=v[i-1][j]+v[i][j-1]-v[i-1][j-1]+(Q[i-1][j-1]<=bs);
    for(int i=H; i<=R; i++)for(int j=W; j<=C; j++)
        is|=(v[i][j]-v[i-H][j]-v[i][j-W]+v[i-H][j-W]>=(H*W+1)/2);
    if(!is)l=bs+1;
    else r=bs;
  }
  return r;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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