# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
591673 | ogibogi2004 | Quality Of Living (IOI10_quality) | C++14 | 5046 ms | 51332 KiB |
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 "quality.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3001;
int table[MAXN][MAXN];
int t1[MAXN][MAXN];
int h,w,r,c;
bool check(int val)
{
for(int i=0;i<MAXN;++i)
{
for(int j=0;j<MAXN;++j)
{
if(table[i][j]<=val)t1[i][j]=1;
else t1[i][j]=0;
}
}
int cnt=0;
for(int i=0;i<h;++i)
{
for(int j=0;j<w;++j)
{
if(t1[i][j])++cnt;
}
}
if(cnt>h*w/2)return 1;
int x=0,y=0;
queue<char>q;
for(int i=0;i<c-w;++i)q.push('R');
q.push('D');
for(int i=0;i<c-w;++i)q.push('L');
q.push('D');
while(x!=r-h||y!=c-w)
{
char dir=q.front();
q.push(q.front());
q.pop();
if(dir=='R')
{
for(int i=x;i<x+h;++i)
{
if(t1[i][y]==1)--cnt;
if(t1[i][y+w]==1)++cnt;
}
++y;
}
else if(dir=='L')
{
for(int i=x;i<x+h;i++)
{
if(t1[i][y+w-1]==1)--cnt;
if(t1[i][y-1]==1)++cnt;
}
--y;
}
else if(dir=='D')
{
for(int j=y;j<y+w;++j)
{
if(t1[x][j]==1)--cnt;
if(t1[x+h][j]==1)++cnt;
}
++x;
}
if(cnt>h*w/2)return 1;
}
return 0;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
r=R;c=C;h=H;w=W;
for(int i=0;i<R;++i)
{
for(int j=0;j<C;++j)
{
table[i][j]=Q[i][j];
}
}
int low=1,high=R*C,mid,best;
while(low<=high)
{
mid=(low+high)/2;
if(check(mid))
{
best=mid;
high=mid-1;
}
else low=mid+1;
}
return best;
}
/*
5 5 3 3
5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15
*/
Compilation message (stderr)
# | 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... |