Submission #766894

#	Time	Username	Problem	Language	Result	Execution time	Memory
766894		irmuun	Quality Of Living (IOI10_quality)	C++17	100 / 100	1334 ms	140156 KiB

quality

#include<bits/stdc++.h>
#include "quality.h"
 
using namespace std;
 
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define all(s) s.begin(),s.end()

int rectangle(int R,int C,int H,int W,int Q[3001][3001]){
    int sum[R+1][C+1],m=H*W/2+1;
    int l=1,r=R*C;
    while(l<r){
        int mid=(l+r)/2;
        bool ok=false;
        sum[0][0]=0;
        for(int i=0;i<=R;i++){
            for(int j=0;j<=C;j++){
                if(i==0||j==0){
                    sum[i][j]=0;
                    continue;
                }
                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(Q[i-1][j-1]<=mid);
                if(i>=H&&j>=W){
                    if(sum[i][j]-sum[i-H][j]-sum[i][j-W]+sum[i-H][j-W]>=m){
                        ok=true;
                    }
                }
            }
        }
        if(ok==true){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    return l;
}

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