This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
// #include "grader.cpp"
#include "quality.h"
using namespace std;
#define cin(vec) for(auto& i : vec) cin >> i
#define cout(vec) for(auto& i : vec) cout << i << " "; cout << "\n";
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define loop(i,a,b) for (int i = a; i < b; i++)
#define F first
#define S second
#define pb(n) push_back(n)
#define pf(n) push_front(n)
#define dci(d) fixed<<setprecision(d)
#define sp ' '
#define el '\n'
#define all(v) v.begin(),v.end()
int pref[3005][3005];
int sub(int i,int j,int k,int l){
return pref[k][l]-pref[k][j-1]-pref[i-1][l]+pref[i-1][j-1];
}
int rectangle(int n, int m, int r, int c, int a[3001][3001]) {
int left=1,right=n*m,ans=1e9;
vector<pair<int,int>>ch(n*m+1);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
ch[a[i][j]]={i,j};
}
}
while(left<=right){
int mid=(left+right)/2;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(i&&j)
pref[i][j]=a[i-1][j-1]<mid;
else
pref[i][j]=0;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
pref[i+1][j+1]+=pref[i+1][j];
}
}
for(int j=0;j<m;j++){
for(int i=0;i<n;i++){
pref[i+1][j+1]+=pref[i][j+1];
}
}
int dec=0;
for(int i=0;i<=n-r;i++){
for(int j=0;j<=m-c;j++){
int num=(ch[mid].F>=i&&ch[mid].F<=(i+r-1)&&ch[mid].S>=j&&ch[mid].S<=(j+c-1));
int x=sub(i+1,j+1,i+r,j+c);
if(x>=r*c-x-num){
dec=1;
if(x==r*c-x-num){
ans=min(ans,mid);
}
}
}
}
if(dec)
right=mid-1;
else
left=mid+1;
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |