Submission #591682

#	Time	Username	Problem	Language	Result	Execution time	Memory
591682		ogibogi2004	Quality Of Living (IOI10_quality)	C++14	100 / 100	1795 ms	210664 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;
char dirs[3*MAXN];
int pref[MAXN][MAXN];
bool check(int val)
{
    for(int i=0;i<r;++i)
    {
        for(int j=0;j<c;++j)
        {
            if(table[i][j]<=val)t1[i][j]=1;
            else t1[i][j]=0;
        }
    }
    pref[0][0]=t1[0][0];
    for(int i=1;i<r;i++)pref[i][0]=pref[i-1][0]+t1[i][0];
    for(int i=1;i<c;i++)pref[0][i]=pref[0][i-1]+t1[0][i];
    for(int i=1;i<r;i++)
    {
        for(int j=1;j<c;j++)
        {
            pref[i][j]=t1[i][j]+pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
        }
    }
    for(int i=0;i<=r-h;i++)
    {
        for(int j=0;j<=c-w;j++)
        {
            int cnt=pref[i+h-1][j+w-1];
            if(i!=0)cnt-=pref[i-1][j+w-1];
            if(j!=0)cnt-=pref[i+h-1][j-1];
            if(i!=0&&j!=0)cnt+=pref[i-1][j-1];
            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 j=0;j<c-w;j++)dirs[j]='R';
    dirs[c-w]='D';
    for(int j=c-w+1;j<(c-w+1)+c-w;j++)dirs[j]='L';
    dirs[(c-w+1)+c-w]='D';
    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:69:12: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |     return best;
      |            ^~~~

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