Submission #545240

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
545240	2022-04-04T04:49:58 Z	AbdelmagedNour	Quality Of Living (IOI10_quality)	C++17	100 / 100	3076 ms	140072 KB

quality

#include "grader.h"
#include<iostream>
using namespace std;
typedef long long ll;
int sum[3001][3001];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    
    
    ll l=0, r=2e9;
    while(l<r) {
	ll mid=(l+r)/2LL;
	//cerr<<l<<" "<<r<<"\n";
	
	for(auto& i:sum)
	for(auto& j:i) j=0;
	
	for(int i=0;i<R;++i) {
	    for(int j=0;j<C;++j) {
		if(mid==Q[i][j]) {
		    sum[i][j]=0;
		}else if(mid<Q[i][j]) {
		    sum[i][j]=1;
		}else {
		    sum[i][j]=-1;
		}
	    }
	}
	
	for(int i=0;i<R;++i) {
	    for(int j=0;j<C;++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];
	    }
	}
	
	bool ok=false;
	for(int i=0;i+H-1<R&&!ok;++i) {
	    for(int j=0;j+W-1<C&&!ok;++j) {
		int x=i+H-1, y=j+W-1;
		int szum=sum[x][y]-(j>0?sum[x][j-1]:0)-(i>0?sum[i-1][y]:0)+(i>0&&j>0?sum[i-1][j-1]:0);
		ok|=szum<=0;
	    }
	}
	
	if(ok) {
	    r=mid;
	}else {
	    l=mid+1;
	}
    }
    
    return l;
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	122 ms	35588 KB	Output is correct
2	Correct	140 ms	35664 KB	Output is correct
3	Correct	124 ms	35668 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	122 ms	35588 KB	Output is correct
2	Correct	140 ms	35664 KB	Output is correct
3	Correct	124 ms	35668 KB	Output is correct
4	Correct	133 ms	35924 KB	Output is correct
5	Correct	126 ms	36016 KB	Output is correct
6	Correct	132 ms	35924 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	122 ms	35588 KB	Output is correct
2	Correct	140 ms	35664 KB	Output is correct
3	Correct	124 ms	35668 KB	Output is correct
4	Correct	133 ms	35924 KB	Output is correct
5	Correct	126 ms	36016 KB	Output is correct
6	Correct	132 ms	35924 KB	Output is correct
7	Correct	149 ms	37608 KB	Output is correct
8	Correct	149 ms	37612 KB	Output is correct
9	Correct	146 ms	37416 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	122 ms	35588 KB	Output is correct
2	Correct	140 ms	35664 KB	Output is correct
3	Correct	124 ms	35668 KB	Output is correct
4	Correct	133 ms	35924 KB	Output is correct
5	Correct	126 ms	36016 KB	Output is correct
6	Correct	132 ms	35924 KB	Output is correct
7	Correct	149 ms	37608 KB	Output is correct
8	Correct	149 ms	37612 KB	Output is correct
9	Correct	146 ms	37416 KB	Output is correct
10	Correct	439 ms	50200 KB	Output is correct
11	Correct	424 ms	50084 KB	Output is correct
12	Correct	274 ms	44876 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	122 ms	35588 KB	Output is correct
2	Correct	140 ms	35664 KB	Output is correct
3	Correct	124 ms	35668 KB	Output is correct
4	Correct	133 ms	35924 KB	Output is correct
5	Correct	126 ms	36016 KB	Output is correct
6	Correct	132 ms	35924 KB	Output is correct
7	Correct	149 ms	37608 KB	Output is correct
8	Correct	149 ms	37612 KB	Output is correct
9	Correct	146 ms	37416 KB	Output is correct
10	Correct	439 ms	50200 KB	Output is correct
11	Correct	424 ms	50084 KB	Output is correct
12	Correct	274 ms	44876 KB	Output is correct
13	Correct	3076 ms	140000 KB	Output is correct
14	Correct	2994 ms	140072 KB	Output is correct
15	Correct	2761 ms	132948 KB	Output is correct