Submission #967528

#	Time	Username	Problem	Language	Result	Execution time	Memory
967528		anango	Quality Of Living (IOI10_quality)	C++17	0 / 100	5044 ms	2396 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int r,c,h,w;
int need;
vector<vector<int>> q;
vector<vector<int>> raw;
vector<vector<int>> pref;


void prefsum() {
    pref=vector<vector<int>>(r+1, vector<int>(c+1,0));
    for (int i=1; i<=r; i++) {
        for (int j=1; j<=c; j++) {
            pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + raw[i-1][j-1];
        }
    }
}

int getrect(int x1, int y1, int x2, int y2) {
    //x1,y1 < x2,y2
    x2++;
    y2++;
    return pref[x2][y2]-pref[x2][y1]-pref[x1][y2]+pref[x1][y1];
}

bool BSTA(int x) {
    for (int i=0; i<r; i++) {
        for (int j=0; j<c; j++) {
            raw[i][j] = (q[i][j]<x);
        }
    }
    prefsum();
    bool work=0;
    for (int i=0; i<r-h+1; i++) {
        for (int j=0; j<c-w+1; j++) {
            int p = (getrect(i,j,i+h-1, j+w-1)>=need);
            //cout << x <<" " << i <<" " << j << " " << i+h <<" " << j+w <<" " << need <<" " << getrect(i,j,i+h-1, j+w-1)<< endl;
            work |= p;

        }
    }
    return work;
    
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    r=R;
    c=C;
    h=H;
    w=W;
    need = h*w;
    need/=2;
    q=vector<vector<int>>(R,vector<int>(C,0));
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            q[i][j] = Q[i][j];
        }
    }
    raw=vector<vector<int>>(r,vector<int>(c,0));

    int l=1;
    int r=R*C;
    while (l<r) {
        int m=(l+r)/2;
        int b=BSTA(m);
        //cout << "res" << " " << m <<" " << b << endl << endl;
        if (b) {
            l=l;   
            r=m;
        }
        else {
            l=m+1;
            r=r;
        }
    }
	while (BSTA(l+1) || l==r*c) l++;
	while (!BSTA(l) || l==1) l--;
    return l;
}

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