Submission #470297

#	Time	Username	Problem	Language	Result	Execution time	Memory
470297		Newtech66	Quality Of Living (IOI10_quality)	C++17	0 / 100	1 ms	332 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;
            //cout<<grid[i][j]<<" ";
        }
        //cout<<endl;
    }
    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];
        }
    }
    /*cout<<endl;
    for(int i=0;i<R;i++)
    {
        for(int j=0;j<C;j++)
        {
            cout<<grid[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;*/
    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;
        //cout<<mid<<endl;
        bool possible=solve(R,C,H,W,Q,mid);
        if(possible)
        {
            if(mid==1)
            {
                ans=1;
                break;
            }
            bool possible2=solve(R,C,H,W,Q,mid-1);
            if(possible2)   r=mid-1;
            else
            {
                ans=mid;
                break;
            }
        }else
        {
            l=mid+1;
        }
    }
	return ans;
}

Compilation message (stderr)

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

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