제출 #775746

#제출 시각아이디문제언어결과실행 시간메모리
775746DobromirAngelov삶의 질 (IOI10_quality)C++14
0 / 100
1 ms596 KiB
#include<bits/stdc++.h> #include "quality.h" using namespace std; const int MAXN=3005; const int INF=1e9+5; int n,m; int h,w; int half; int pref[MAXN][MAXN]; int minPoss[MAXN][MAXN]; bool check(int x,int q[][3001]) { pref[0][0]=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(i>0 && j>0) pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]; else if(i>0) pref[i][j]=pref[i-1][j]; else if(j>0) pref[i][j]=pref[i][j-1]; if(q[i][j]<x) pref[i][j]++; if(i>=h-1 && j>=w-1) { int a1=0,a2=0,b=0; if(i>=h) a1=pref[i-h][j]; if(j>=w) a2=pref[i][j-w]; if(i>=h && j>=w) b=pref[i-h][j-w]; if(pref[i][j]-a1-a2+b>=half) return 1; } } } return 0; } int find_ans(int x,int q[][3001]) { deque<int> dq; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { while(!dq.empty() && dq.front()<=j-w) dq.pop_front(); if(q[i][j]>=x) { while(!dq.empty() && q[i][j]<q[i][dq.back()]) dq.pop_back(); dq.push_back(j); } if(!dq.empty()) minPoss[i][j]=q[i][dq.front()]; else minPoss[i][j]=INF; } while(!dq.empty()) dq.pop_back(); } for(int j=0;j<m;j++) { for(int i=0;i<n;i++) { while(!dq.empty() && dq.front()<=i-h) dq.pop_front(); if(minPoss[i][j]>=x) { while(!dq.empty() && minPoss[i][j]<minPoss[dq.back()][j]) dq.pop_back(); dq.push_back(i); } if(!dq.empty()) minPoss[i][j]=minPoss[dq.front()][j]; else minPoss[i][j]=INF; } while(!dq.empty()) dq.pop_back(); } int ans=INF; pref[0][0]=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(i>0 && j>0) pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]; else if(i>0) pref[i][j]=pref[i-1][j]; else if(j>0) pref[i][j]=pref[i][j-1]; if(q[i][j]<x) pref[i][j]++; if(i>=h-1 && j>=w-1) { int a1=0,a2=0,b=0; if(i>=h) a1=pref[i-h][j]; if(j>=w) a2=pref[i][j-w]; if(i>=h && j>=w) b=pref[i-h][j-w]; if(pref[i][j]-a1-a2+b>=half) ans=min(ans, minPoss[i][j]); } } } return ans; } int rectangle(int R,int C,int H,int W,int q[3001][3001]) { n=R, m=C; h=H, w=W; half=h*w/2; int l=1,r=n*m; while(l<r) { int mid=(l+r)/2; if(check(mid,q)) r=mid; else l=mid+1; } return find_ans(l,q); }
#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...