oj.uz

답안 #241558

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
241558 2020-06-24T12:49:59 Z davi_bart 삶의 질 (IOI10_quality) C++14
0 / 100
 5 ms 640 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
#define ll long long
//#define int ll
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int x[3001][3001];
bool c(int k,int R,int C,int H,int W,int Q[3001][3001]){
  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
      x[i][j]=0;
    }
  }
  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
      x[i][j]=Q[i][j]<k;
      if(j>0)x[i][j]+=x[i][j-1];
    }
  }
  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
      if(i>0)x[i][j]+=x[i-1][j];
    }
  }
  for(int i=H-1;i<R;i++){
    for(int j=W-1;j<C;j++){
      int z=x[i][j];
      if(i>H-1)z-=x[i-H][j];
      if(j>W-1)z-=x[i][j-W];
      if(i>=H && j>=W)z+=x[i-H][j-W];
      if(z>=(H*W/2)){
          return 1;
      }
    }
  }
  return 0;
}
int sol(int k,int R,int C,int H,int W,int Q[3001][3001]){
  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
      x[i][j]=0;
    }
  }
  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
      x[i][j]=Q[i][j]<k;
      if(j>0)x[i][j]+=x[i][j-1];
    }
  }
  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
      if(i>0)x[i][j]+=x[i-1][j];
    }
  }
  int mi=1000000000;
  for(int i=H-1;i<R;i++){
    for(int j=W-1;j<C;j++){
      int z=x[i][j];
      if(i>H-1)z-=x[i-H][j];
      if(j>W-1)z-=x[i][j-W];
      if(i>=H && j>=W)z+=x[i-H][j-W];
      if(z>=(H*W/2)){
          for(int a=i-H+1;a<=i;a++){
            for(int b=j-W+1;b<=j;b++){
              if(Q[a][b]>k)mi=min(mi,Q[a][b]);
            }
          }
      }
    }
  }
  return mi;
}
int rectangle(int R,int C,int H,int W,int Q[3001][3001]) {
	int l=1,r=R*C+1;
	while(l<r-1){
    int m=(l+r)/2;
    if(c(m,R,C,H,W,Q))r=m;
    else l=m;
	}
	return sol(r,R,C,H,W,Q);
}/*
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int R,C,H,W;
    cin>>R>>C>>H>>W;
    int Q[3001][3001];
    for(int i=0;i<R;i++){
      for(int j=0;j<C;j++){
        cin>>Q[i][j];
      }
    }
    cout<<rectangle(R,C,H,W,Q);
}*/
/*
5 5 3 3
5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15
*/

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Incorrect 5 ms 640 KB Output isn't correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Incorrect 5 ms 640 KB Output isn't correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Incorrect 5 ms 640 KB Output isn't correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Incorrect 5 ms 640 KB Output isn't correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Incorrect 5 ms 640 KB Output isn't correct