Submission #587438

#	Time	Username	Problem	Language	Result	Execution time	Memory
587438		Omar_Elgedawy	Quality Of Living (IOI10_quality)	C++14	80 / 100	4686 ms	262144 KiB

quality

#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[3002][3002];
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;
    map<int,pair<int,int>>ch;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;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 i=0;i<=n;i++){
        //     for(int j=0;j<=m;j++){
        //         cout<<pref[i][j]<<' ';
        //     }cout<<el;
        // }cout<<el;
        for(int j=0;j<m;j++){
            for(int i=0;i<n;i++){
                pref[i+1][j+1]+=pref[i][j+1];
            }
        }
        // for(int i=0;i<=n;i++){
        //     for(int j=0;j<=m;j++){
        //         cout<<pref[i][j]<<' ';
        //     }cout<<el;
        // }cout<<el;
        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){
                        // cout<<i<<' '<<j<<' '<<i+r-1<<' '<<j+c-1<<' '<<x<<' '<<mid<<el<<el;
                        ans=min(ans,mid);
                    }
                }
            }
        }
        // cout<<dec<<el;
        if(dec)
            right=mid-1;
        else 
            left=mid+1;
    }
	return ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 20