oj.uz

답안 #406938

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
406938 2021-05-18T08:50:56 Z pliam 삶의 질 (IOI10_quality) C++14
40 / 100
 5000 ms 145284 KB 
#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXR 3005
#define MAXC 3005
#define INF (int)1e9

int st[4*MAXR*MAXC];
int min_med=INF;
int h,w,r,c,q[3005][3005];

void update(int pos,int val,int v=1,int start=1,int end=r*c){
	if(start==end){
		st[v]+=val;
		return;
	}
	int mid=(start+end)/2;
	if(pos<=mid){
		update(pos,val,2*v,start,mid);
	}else{
		update(pos,val,2*v+1,mid+1,end);
	}
	st[v]=st[2*v]+st[2*v+1];
}

int find_k(int k,int v=1,int start=1,int end=r*c){
	if(start==end){
		return start;
	}
	int mid=(start+end)/2;
	if(st[2*v]>=k){
		return find_k(k,2*v,start,mid);
	}else{
		return find_k(k-st[2*v],2*v+1,mid+1,end);
	}
}

int median(){
	return find_k((h*w+1)/2);
}

void brute_force(int x){
	memset(st,0,sizeof(st));
	for(int y=0;y<w;y++){
		for(int x_=x-h+1;x_<=x;x_++){
			update(q[x_][y],1);
		}
	}
	min_med=min(min_med,median());
	for(int y=w;y<c;y++){
		for(int x_=x-h+1;x_<=x;x_++){
			update(q[x_][y],1);
			update(q[x_][y-w],-1);
		}
		min_med=min(min_med,median());
	}
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	memset(st,0,sizeof(st));
	r=R;
	c=C;
	h=H;
	w=W;
	for(int a=0;a<r;a++){
		for(int b=0;b<c;b++){
			q[a][b]=Q[a][b];
		}
	}
	for(int a=h-1;a<r;a++){
		brute_force(a);
	}
	
	return min_med;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 318 ms 141856 KB Output is correct
2 Correct 399 ms 141904 KB Output is correct
3 Correct 104 ms 141904 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 318 ms 141856 KB Output is correct
2 Correct 399 ms 141904 KB Output is correct
3 Correct 104 ms 141904 KB Output is correct
4 Correct 1091 ms 142580 KB Output is correct
5 Correct 1373 ms 142572 KB Output is correct
6 Correct 700 ms 142580 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 318 ms 141856 KB Output is correct
2 Correct 399 ms 141904 KB Output is correct
3 Correct 104 ms 141904 KB Output is correct
4 Correct 1091 ms 142580 KB Output is correct
5 Correct 1373 ms 142572 KB Output is correct
6 Correct 700 ms 142580 KB Output is correct
7 Correct 4680 ms 145280 KB Output is correct
8 Correct 4673 ms 145284 KB Output is correct
9 Execution timed out 5049 ms 145068 KB Time limit exceeded

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 318 ms 141856 KB Output is correct
2 Correct 399 ms 141904 KB Output is correct
3 Correct 104 ms 141904 KB Output is correct
4 Correct 1091 ms 142580 KB Output is correct
5 Correct 1373 ms 142572 KB Output is correct
6 Correct 700 ms 142580 KB Output is correct
7 Correct 4680 ms 145280 KB Output is correct
8 Correct 4673 ms 145284 KB Output is correct
9 Execution timed out 5049 ms 145068 KB Time limit exceeded

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 318 ms 141856 KB Output is correct
2 Correct 399 ms 141904 KB Output is correct
3 Correct 104 ms 141904 KB Output is correct
4 Correct 1091 ms 142580 KB Output is correct
5 Correct 1373 ms 142572 KB Output is correct
6 Correct 700 ms 142580 KB Output is correct
7 Correct 4680 ms 145280 KB Output is correct
8 Correct 4673 ms 145284 KB Output is correct
9 Execution timed out 5049 ms 145068 KB Time limit exceeded