oj.uz

Submission #283567

# Submission time Handle Problem Language Result Execution time Memory
283567 2020-08-26T01:42:47 Z tinjyu Quality Of Living (IOI10_quality) C++14
100 / 100
 3687 ms 246216 KB 
#include "quality.h"
#include <iostream>
using namespace std;
long long int h,w,r,c,sum[3005][3005],a[3005][3005];
bool check(){
	for(int i=0;i<r;i++)
	{
		for(int j=0;j<c;j++)
		{
			sum[i][j]=a[i][j];
			if(i>0)sum[i][j]+=sum[i-1][j];
			if(j>0)sum[i][j]+=sum[i][j-1];
			if(i>0 && j>0)sum[i][j]-=sum[i-1][j-1];
			//cout<<sum[i][j]<<" ";
		}
		//cout<<endl;
	}
	for(int i=h-1;i<r;i++)
	{
		for(int j=w-1;j<c;j++)
		{
			int now=sum[i][j];
			if(i-h>=0)now-=sum[i-h][j];

			if(j-w>=0)now-=sum[i][j-w];

			if(i-h>=0 && j-w>=0)now+=sum[i-h][j-w];
			//cout<<i<<" "<<j<<" "<<now<<endl;

			if(now<=0)return 1;
		}
	}
	return 0;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	long long int ans,le=1,ri=R*C;
	h=H;
	w=W;
	r=R;
	c=C;
	while(le<=ri)
	{
		int mid=(le+ri)/2;
		//cout<<mid<<endl;
		for(int i=0;i<R;i++)
		{
			for(int j=0;j<C;j++)
			{
				if(Q[i][j]<mid)a[i][j]=-1;
				if(Q[i][j]==mid)a[i][j]=0;
				if(Q[i][j]>mid)a[i][j]=1;
				//cout<<a[i][j]<<" ";
			}
			//cout<<endl;
		}
		if(check()==1)
		{
			ans=mid;
			ri=mid-1;
		}
		else le=mid+1;
	}
	return ans;
}

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 4 ms 1824 KB Output is correct
5 Correct 4 ms 1792 KB Output is correct
6 Correct 4 ms 1792 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 4 ms 1824 KB Output is correct
5 Correct 4 ms 1792 KB Output is correct
6 Correct 4 ms 1792 KB Output is correct
7 Correct 37 ms 6272 KB Output is correct
8 Correct 32 ms 6272 KB Output is correct
9 Correct 33 ms 6016 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 4 ms 1824 KB Output is correct
5 Correct 4 ms 1792 KB Output is correct
6 Correct 4 ms 1792 KB Output is correct
7 Correct 37 ms 6272 KB Output is correct
8 Correct 32 ms 6272 KB Output is correct
9 Correct 33 ms 6016 KB Output is correct
10 Correct 423 ms 38648 KB Output is correct
11 Correct 377 ms 38776 KB Output is correct
12 Correct 195 ms 25592 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 4 ms 1824 KB Output is correct
5 Correct 4 ms 1792 KB Output is correct
6 Correct 4 ms 1792 KB Output is correct
7 Correct 37 ms 6272 KB Output is correct
8 Correct 32 ms 6272 KB Output is correct
9 Correct 33 ms 6016 KB Output is correct
10 Correct 423 ms 38648 KB Output is correct
11 Correct 377 ms 38776 KB Output is correct
12 Correct 195 ms 25592 KB Output is correct
13 Correct 3644 ms 246216 KB Output is correct
14 Correct 3687 ms 246200 KB Output is correct
15 Correct 3314 ms 238976 KB Output is correct