oj.uz

답안 #976441

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
976441 2024-05-06T14:56:24 Z LaviniaTornaghi 삶의 질 (IOI10_quality) C++14
60 / 100
 5000 ms 35156 KB 
#include <bits/stdc++.h>
using namespace std;
#include "grader.h"

void print(multiset<int> x){
	for(auto i:x) cout<<i<<" ";
	cout<<endl;
}

int A,B;

void addcolumn(vector<vector<int>> &q, multiset <int> &s, int c, int sq, int eq){
	assert(eq<=A);
	for(int i=sq;i<eq;i++) s.insert(q[i][c]);
}
void removecolumn(vector<vector<int>> &q,multiset <int> &s, int c, int sq, int eq){
	assert(eq<=A);
	for(int i=sq;i<eq;i++){
		s.erase(s.lower_bound(q[i][c]));
	}
}
void addrow(vector<vector<int>> &q, multiset <int> &s, int r, int sq, int eq){
	assert(eq<=B);
	for(int i=sq;i<eq;i++) s.insert(q[r][i]);
}
void removerow(vector<vector<int>> &q, multiset <int> &s, int r, int sq, int eq){
	assert(eq<=B);
	for(int i=sq;i<eq;i++){
		s.erase(s.lower_bound(q[r][i]));
	}
}
int getmed(multiset<int>&s){
	/*int l = *(s.begin()), r = *(s.rbegin());
	while(r-l>1){
		int m = (l+r)/2;
		if( (s.lower_bound(m) - s.begin()) >(s.size()/2)) m = r;
		else l = m;
	}
	return l;*/
	auto x = s.begin();
	advance(x,s.size()/2);
	return *x;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	vector<vector<int>> q(R,vector<int>(C)); A=R, B=C;
	for(int i=0;i<R;i++)
		for(int j=0;j<C;j++)
			q[i][j]=Q[i][j];
	
	multiset<int> s;
	int ans = INT_MAX;
	for(int i=0;i<H;i++)
		for(int j=0;j<W;j++)
			s.insert(q[i][j]);
	for(int i=0;i<=R-H;i++){
		if(!(i%2)){
			for(int j=1;j<=C-W;j++){
				ans = min(ans, getmed(s));
				removecolumn(q,s,j-1,i,i+H);
				addcolumn(q,s,j+W-1,i,i+H);
			}
			ans = min(ans,getmed(s));
			removerow(q,s,i,C-W,C);
			if(i+H<R)addrow(q,s,i+H,C-W,C);
		}else{
			for(int j=C-W-1;j>=0;j--){
				ans = min(ans, getmed(s));
				removecolumn(q,s,j+W,i,i+H);
				addcolumn(q,s,j,i,i+H);
			}
			ans = min(ans,getmed(s));
			removerow(q,s,i,0,W);
			if(i+H<R) addrow(q,s,i+H,0,W);
		}
	}
	return ans;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 31 ms 2652 KB Output is correct
5 Correct 40 ms 2648 KB Output is correct
6 Correct 20 ms 2916 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 31 ms 2652 KB Output is correct
5 Correct 40 ms 2648 KB Output is correct
6 Correct 20 ms 2916 KB Output is correct
7 Correct 4848 ms 6772 KB Output is correct
8 Correct 288 ms 7424 KB Output is correct
9 Correct 3769 ms 6164 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 31 ms 2652 KB Output is correct
5 Correct 40 ms 2648 KB Output is correct
6 Correct 20 ms 2916 KB Output is correct
7 Correct 4848 ms 6772 KB Output is correct
8 Correct 288 ms 7424 KB Output is correct
9 Correct 3769 ms 6164 KB Output is correct
10 Execution timed out 5034 ms 35156 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 31 ms 2652 KB Output is correct
5 Correct 40 ms 2648 KB Output is correct
6 Correct 20 ms 2916 KB Output is correct
7 Correct 4848 ms 6772 KB Output is correct
8 Correct 288 ms 7424 KB Output is correct
9 Correct 3769 ms 6164 KB Output is correct
10 Execution timed out 5034 ms 35156 KB Time limit exceeded
11 Halted 0 ms 0 KB -