Submission #591672

#	Time	Username	Problem	Language	Result	Execution time	Memory
591672		ogibogi2004	Quality Of Living (IOI10_quality)	C++14	60 / 100	5030 ms	58164 KiB

quality

#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;

}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:90:12: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |     return best;
      |            ^~~~

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