Submission #286942

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
286942	2020-08-31T07:37:08 Z	mraron	Quality Of Living (IOI10_quality)	C++14	100 / 100	4486 ms	140480 KB

quality

#include "quality.h"
#include<bits/stdc++.h>
using namespace std;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int can=R*C;
	vector<vector<int>> t(R, vector<int>(C));

	for(int i=25;i>=0;i--) {
		int akt=can-(1<<i);
		if(akt>=1) {
			for(int i=0;i<R;++i) {
				for(int j=0;j<C;++j) {
					if(akt==Q[i][j]) t[i][j]=0;
					else if(akt<Q[i][j]) t[i][j]=1;
					else if(akt>Q[i][j]) t[i][j]=-1;
				}
			}
			
			for(int i=0;i<R;++i) {
				for(int j=0;j<C;++j) {
					if(i) t[i][j]+=t[i-1][j];
					if(j) t[i][j]+=t[i][j-1];
					if(i&&j) t[i][j]-=t[i-1][j-1];
				}
			}
			
			bool ok=false;
			for(int i=0;!ok&&i+H-1<R;++i) {
				for(int j=0;!ok&&j+W-1<C;++j) {
					int sum=t[i+H-1][j+W-1];
					if(i) sum-=t[i-1][j+W-1];
					if(j) sum-=t[i+H-1][j-1];
					if(i&&j) sum+=t[i-1][j-1];
					if(sum<=0) ok=true;
				}
			}
			
			if(ok) can=akt;
		}
	}
	
	return can;
	
}

Subtask #1

20.0 / 20.0

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

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	4 ms	768 KB	Output is correct
5	Correct	4 ms	768 KB	Output is correct
6	Correct	4 ms	768 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	4 ms	768 KB	Output is correct
5	Correct	4 ms	768 KB	Output is correct
6	Correct	4 ms	768 KB	Output is correct
7	Correct	35 ms	2176 KB	Output is correct
8	Correct	35 ms	2176 KB	Output is correct
9	Correct	33 ms	2176 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	4 ms	768 KB	Output is correct
5	Correct	4 ms	768 KB	Output is correct
6	Correct	4 ms	768 KB	Output is correct
7	Correct	35 ms	2176 KB	Output is correct
8	Correct	35 ms	2176 KB	Output is correct
9	Correct	33 ms	2176 KB	Output is correct
10	Correct	439 ms	12152 KB	Output is correct
11	Correct	438 ms	12280 KB	Output is correct
12	Correct	217 ms	8440 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	4 ms	768 KB	Output is correct
5	Correct	4 ms	768 KB	Output is correct
6	Correct	4 ms	768 KB	Output is correct
7	Correct	35 ms	2176 KB	Output is correct
8	Correct	35 ms	2176 KB	Output is correct
9	Correct	33 ms	2176 KB	Output is correct
10	Correct	439 ms	12152 KB	Output is correct
11	Correct	438 ms	12280 KB	Output is correct
12	Correct	217 ms	8440 KB	Output is correct
13	Correct	4486 ms	71080 KB	Output is correct
14	Correct	4470 ms	140480 KB	Output is correct
15	Correct	3965 ms	129784 KB	Output is correct