#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;
map<int,pair<int,int>>ch;
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
5 ms |
1744 KB |
Output is correct |
5 |
Correct |
6 ms |
1748 KB |
Output is correct |
6 |
Correct |
7 ms |
1704 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
5 ms |
1744 KB |
Output is correct |
5 |
Correct |
6 ms |
1748 KB |
Output is correct |
6 |
Correct |
7 ms |
1704 KB |
Output is correct |
7 |
Correct |
68 ms |
8996 KB |
Output is correct |
8 |
Correct |
46 ms |
9016 KB |
Output is correct |
9 |
Correct |
54 ms |
8424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
5 ms |
1744 KB |
Output is correct |
5 |
Correct |
6 ms |
1748 KB |
Output is correct |
6 |
Correct |
7 ms |
1704 KB |
Output is correct |
7 |
Correct |
68 ms |
8996 KB |
Output is correct |
8 |
Correct |
46 ms |
9016 KB |
Output is correct |
9 |
Correct |
54 ms |
8424 KB |
Output is correct |
10 |
Correct |
1426 ms |
78772 KB |
Output is correct |
11 |
Correct |
1186 ms |
78860 KB |
Output is correct |
12 |
Correct |
647 ms |
43508 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
5 ms |
1744 KB |
Output is correct |
5 |
Correct |
6 ms |
1748 KB |
Output is correct |
6 |
Correct |
7 ms |
1704 KB |
Output is correct |
7 |
Correct |
68 ms |
8996 KB |
Output is correct |
8 |
Correct |
46 ms |
9016 KB |
Output is correct |
9 |
Correct |
54 ms |
8424 KB |
Output is correct |
10 |
Correct |
1426 ms |
78772 KB |
Output is correct |
11 |
Correct |
1186 ms |
78860 KB |
Output is correct |
12 |
Correct |
647 ms |
43508 KB |
Output is correct |
13 |
Runtime error |
4689 ms |
262144 KB |
Execution killed with signal 9 |
14 |
Halted |
0 ms |
0 KB |
- |