(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 #587445

#TimeUsernameProblemLanguageResultExecution timeMemory
587445Omar_ElgedawyQuality Of Living (IOI10_quality)C++14
100 / 100
3183 ms141676 KiB
#include <bits/stdc++.h> // #include "grader.cpp" #include "quality.h" using namespace std; #define cin(vec) for(auto& i : vec) cin >> i #define cout(vec) for(auto& i : vec) cout << i << " "; cout << "\n"; #define fast ios::sync_with_stdio(0);cin.tie(0); #define loop(i,a,b) for (int i = a; i < b; i++) #define F first #define S second #define pb(n) push_back(n) #define pf(n) push_front(n) #define dci(d) fixed<<setprecision(d) #define sp ' ' #define el '\n' #define all(v) v.begin(),v.end() int pref[3005][3005]; int sub(int i,int j,int k,int l){ return pref[k][l]-pref[k][j-1]-pref[i-1][l]+pref[i-1][j-1]; } int rectangle(int n, int m, int r, int c, int a[3001][3001]) { int left=1,right=n*m,ans=1e9; vector<pair<int,int>>ch(n*m+1); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ ch[a[i][j]]={i,j}; } } while(left<=right){ int mid=(left+right)/2; for(int i=0;i<=n;i++){ for(int j=0;j<=m;j++){ if(i&&j) pref[i][j]=a[i-1][j-1]<mid; else pref[i][j]=0; } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ pref[i+1][j+1]+=pref[i+1][j]; } } for(int j=0;j<m;j++){ for(int i=0;i<n;i++){ pref[i+1][j+1]+=pref[i][j+1]; } } int dec=0; for(int i=0;i<=n-r;i++){ for(int j=0;j<=m-c;j++){ int num=(ch[mid].F>=i&&ch[mid].F<=(i+r-1)&&ch[mid].S>=j&&ch[mid].S<=(j+c-1)); int x=sub(i+1,j+1,i+r,j+c); if(x>=r*c-x-num){ dec=1; if(x==r*c-x-num){ ans=min(ans,mid); } } } } if(dec) right=mid-1; else left=mid+1; } return ans; }
#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...