Submission #1100814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100814		Alexandre	Quality Of Living (IOI10_quality)	C++14	0 / 100	2 ms	14672 KiB

quality

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

const int MAXN = 3100;
int m[MAXN][MAXN], SP[MAXN][MAXN], h[MAXN][MAXN], has[MAXN][MAXN], SPH[MAXN][MAXN];

bool teste(int v,int R, int C, int H, int W){
    
    for(int i = 1; i <= R; i++){
        for(int j = 1; j <= C; j++){
            
            SP[i][j] = 0;
            h[i][j] = 0;
            has[i][j] = 0;
            SPH[i][j] = 0;
            
        }
    }
    
    for(int i = 1; i <= R; i++){
       
        for(int j = 1; j <= C; j++){
           
            if(m[i][j]<v){
               
                h[i][j] = 1;
               
            }else{
               
                h[i][j] = 0;
               
            }
            
            if(m[i][j]==v) has[i][j] = 1;
           
            if(i==1 && j==1){
                SP[i][j] = h[i][j];
                continue;
            }
            if(i==1){
                SP[i][j] = SP[i][j-1] + h[i][j];
                continue;
            }
            if(j==1){
                SP[i][j] = SP[i-1][j] + h[i][j];
                continue;
            }
            SP[i][j] = SP[i-1][j] + SP[i][j-1] - SP[i-1][j-1] + h[i][j];
           
        }
       
    }
    
    for(int i = 1; i <= R; i++){
        
        for(int j = 1; j <= C; j++){
           
            if(i==1 && j==1){
                SPH[i][j] = has[i][j];
                continue;
            }
            if(i==1){
                SPH[i][j] = SPH[i][j-1] + has[i][j];
                continue;
            }
            if(j==1){
                SPH[i][j] = SPH[i-1][j] + has[i][j];
                continue;
            }
            SPH[i][j] = SPH[i-1][j] + SPH[i][j-1] - SPH[i-1][j-1] + has[i][j];
            
        }
    }
   
    for(int i = H; i <= R; i++){
       
        for(int j = W; j <= C; j++){
           
           int total = SP[i][j] - SP[i][j-W] - SP[i-H][j] + SP[i-H][j-W];
           int contem = SPH[i][j] - SPH[i][j-W] - SPH[i-H][j] + SPH[i-H][j-W];
           if((total == (H*W-1)/2) && contem!=0) return true;
           
        }
       
    }
   
    return false;
}

int bb(int R, int C, int H, int W){
   
    int ini = 1;
    int fim = R*C;
   
    while(ini<fim){
       
        int m = (ini+fim)/2;
        if(teste(m,R,C,H,W)){
           
            fim = m;
           
        }else{
           
            ini = m + 1;
           
        }
       
    }
   
    return fim;
   
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	
	for(int i = 1; i <= R; i++){
		
		for(int j = 1; j <= C; j++){
			
			m[i][j] = Q[i-1][j-1];
			
		}
		
	}
	
	return bb(R,C,H,W);
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20