Submission #470301

#	Time	Username	Problem	Language	Result	Execution time	Memory
470301		Newtech66	Quality Of Living (IOI10_quality)	C++17	100 / 100	3449 ms	140428 KiB

quality

#include "quality.h"
#include<vector>
#include<iostream>
using namespace std;

bool solve(int R, int C, int H, int W, int Q[3001][3001],int mid)
{
    vector<vector<int> > grid(R,vector<int>(C));
    for(int i=0;i<R;i++)
    {
        for(int j=0;j<C;j++)
        {
            if(Q[i][j]<=mid)    grid[i][j]=-1;
            else    grid[i][j]=1;
        }
    }
    for(int j=1;j<C;j++)
    {
        grid[0][j]+=grid[0][j-1];
    }
    for(int i=1;i<R;i++)
    {
        grid[i][0]+=grid[i-1][0];
    }
    for(int i=1;i<R;i++)
    {
        for(int j=1;j<C;j++)
        {
            grid[i][j]+=grid[i-1][j]+grid[i][j-1]-grid[i-1][j-1];
        }
    }
    for(int i=H-1;i<R;i++)
    {
        for(int j=W-1;j<C;j++)
        {
            int chk=grid[i][j];
            if(i>=H)    chk-=grid[i-H][j];
            if(j>=W)    chk-=grid[i][j-W];
            if(i>=H && j>=W)    chk+=grid[i-H][j-W];
            if(chk<0)   return true;
        }
    }
    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    int l=1,r=R*C;
    int mid,ans;
    while(l<r)
    {
        mid=l+(r-l)/2;
        bool possible=solve(R,C,H,W,Q,mid);
        if(possible)
        {
            ans=mid;
            r=mid-1;
        }else
        {
            l=mid+1;
        }
    }
    if(l==r && solve(R,C,H,W,Q,l))    ans=min(l,ans);
    return ans;
}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:48:13: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |     int mid,ans;
      |             ^~~

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