Submission #288016

#	Time	Username	Problem	Language	Result	Execution time	Memory
288016		FEDIKUS	Quality Of Living (IOI10_quality)	C++17	100 / 100	2273 ms	122944 KiB

quality

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define up(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#include "quality.h"

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;

int pom[3001][3001];

bool moze(int a,int R,int C,int H,int W,int** Q){
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            pom[i][j]=(Q[i][j]<=a);
            if(i>0) pom[i][j]+=pom[i-1][j];
            if(j>0) pom[i][j]+=pom[i][j-1];
            if(i>0 && j>0) pom[i][j]-=pom[i-1][j-1];
        }
    }
    for(int i=H-1;i<R;i++){
        for(int j=W-1;j<C;j++){
            int sta=0;
            sta+=pom[i][j];
            if(i>H-1) sta-=pom[i-H][j];
            if(j>W-1) sta-=pom[i][j-W];
            if(i>H-1 && j>W-1) sta+=pom[i-H][j-W];
            if(sta>=W*H/2+1) return true;
        }
    }
    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    int ret=-1;
    int** novoQ=new int*[3001];
    for(int i=0;i<=3000;i++){
        novoQ[i]=new int[3001];
    }
    for(int i=0;i<=3000;i++){
        for(int j=0;j<3000;j++) novoQ[i][j]=Q[i][j];
    }
    int l=1;
    int r=R*C;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(moze(mid,R,C,H,W,novoQ)){
            ret=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    return ret;
}

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