(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

Submission #410240

#TimeUsernameProblemLanguageResultExecution timeMemory
410240pliamQuality Of Living (IOI10_quality)C++14
100 / 100
2498 ms121584 KiB
#include "quality.h" #include <bits/stdc++.h> using namespace std; #define MAXR 3005 #define MAXC 3005 #define INF (int)1e9 int height,width,rows,cols; int q[3005][3005]; int cnt[3005]; bool check(int x){ for(int c=1;c<=cols;c++){ cnt[c]=0; for(int r=1;r<height;r++){ cnt[c]+=(q[r][c]<=x); } } for(int r=1;r+height-1<=rows;r++){ //update for(int c=1;c<=cols;c++){ cnt[c]+=((q[r+height-1][c]<=x)-(q[r-1][c]<=x)); } int ctr=0; for(int c=1;c<width;c++){ ctr+=cnt[c]; } //slide for(int c=1;c+width-1<=cols;c++){ //update ctr+=(cnt[c+width-1]-cnt[c-1]); if(ctr>=((height*width+1)/2)){ return true; } } } return false; } int rectangle(int R, int C, int H, int W, int Q[3001][3001]) { rows=R; cols=C; height=H; width=W; for(int r=0;r<rows;r++){ for(int c=0;c<cols;c++){ q[r+1][c+1]=Q[r][c]; } } for(int r=1;r<=rows;r++){ q[r][0]=INF; } for(int c=1;c<=cols;c++){ q[0][c]=INF; } //binary search int k=R*C; for(int b=R*C-1;b>0;b/=2){ while(k-b>0&&check(k-b)) k-=b; } return k; }
#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...