제출 #406938

#제출 시각아이디문제언어결과실행 시간메모리
406938pliam삶의 질 (IOI10_quality)C++14
40 / 100
5049 ms145284 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...