Submission #965416

#	Time	Username	Problem	Language	Result	Execution time	Memory
965416		hirayuu_oj	Quality Of Living (IOI10_quality)	C++17	100 / 100	1744 ms	140412 KiB

quality

#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end();
using ll=long long;
const ll INF=1LL<<60;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    vector<vector<int>> cum(R+1,vector<int>(C+1,0));
    int ok=R*C,ng=0;
    while(ok-ng>1){
        int mid=(ok+ng)/2;
        rep(i,R+1){
            cum[i][0]=0;
        }
        rep(i,C+1){
            cum[0][i]=0;
        }
        rep(i,R){
            rep(j,C){
                cum[i+1][j+1]=cum[i+1][j]+cum[i][j+1]-cum[i][j];
                if(Q[i][j]<=mid)cum[i+1][j+1]++;
            }
        }
        bool can=false;
        rep(i,R-H+1){
            rep(j,C-W+1){
                int val=cum[i+H][j+W]-cum[i+H][j]-cum[i][j+W]+cum[i][j];
                if(val>=H*W-val)can=true;
            }
        }
        if(can)ok=mid;
        else ng=mid;
    }
    return ok;
}
//g++ -o quality -O2 quality.cpp grader.cpp

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