제출 #290043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
290043		dolijan	삶의 질 (IOI10_quality)	C++14	0 / 100	1 ms	768 KiB

quality

#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
using namespace std;
const int mn=3001;
bool moze(int r,int c,int h,int w,int q[mn][mn],int kolko)
{
	int dp[mn][mn];
	for(int i=0;i<r;i++)
		for(int j=0;j<c;j++) dp[i][j]=0;
	if(q[0][0]<kolko) dp[0][0]=1;
	for(int i=1;i<r;i++) dp[i][0]=dp[i-1][0]+(q[i][0]<kolko);
	for(int j=1;j<c;j++) dp[0][j]=dp[0][j-1]+(q[0][j]<kolko);
	for(int i=1;i<r;i++)
	{
		for(int j=1;j<c;j++)
		{
			dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+(q[i][j]<kolko);
		}
	}
	int pola=(h*w)/2;
	for(int i=h-1;i<r;i++)
	{
		for(int j=w-1;j<c;j++)
		{
			int kolko=dp[i][j];
			if(i>=h)
			{
				kolko-=dp[i-h][j];
			}
			if(j>=w)
			{
				kolko-=dp[i][j-w];
			}
			if(i>=h && j>=w)
			{
				kolko+=dp[i-h][j-w];
			}
			if(kolko>=pola) return true;
		}
	}
	return false;
}
int rectangle1(int r,int c,int h,int w,int q[mn][mn])
{
	int ll=1,rr=r*c;
	while(ll<rr)
	{
		int mid=(ll+rr)/2;
		if(moze(r,c,h,w,q,mid)) rr=mid-1;
		else ll=mid+1;
	}
	return rr;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	return rectangle1(R,C,H,W,Q);
}
/*
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int r,c,h,w;
	cout<<"aaaaa"<<endl;
	cin>>r>>c>>h>>w;
	int a[mn][mn];
	for(int i=0;i<r;i++)
		for(int j=0;j<c;j++) cin>>a[i][j];
	cout<<rectangle(r,c,h,w,a)<<endl;
	return 0;
}*/

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