oj.uz

Submission #967535

# Submission time Handle Problem Language Result Execution time Memory
967535 2024-04-22T11:13:56 Z anango Quality Of Living (IOI10_quality) C++17
100 / 100
 1957 ms 246608 KB 
#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-1 <<" " << j+w-1 <<" " << 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;
        }
    } //BSTA(l) = is l high enough
	while (BSTA(l-1)) l--;
	while (!BSTA(l)) l++;
    assert(BSTA(l));
    return l;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2648 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2648 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 15 ms 6592 KB Output is correct
8 Correct 14 ms 6500 KB Output is correct
9 Correct 15 ms 6392 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2648 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 15 ms 6592 KB Output is correct
8 Correct 14 ms 6500 KB Output is correct
9 Correct 15 ms 6392 KB Output is correct
10 Correct 204 ms 35508 KB Output is correct
11 Correct 181 ms 35412 KB Output is correct
12 Correct 96 ms 24108 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2648 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 15 ms 6592 KB Output is correct
8 Correct 14 ms 6500 KB Output is correct
9 Correct 15 ms 6392 KB Output is correct
10 Correct 204 ms 35508 KB Output is correct
11 Correct 181 ms 35412 KB Output is correct
12 Correct 96 ms 24108 KB Output is correct
13 Correct 1957 ms 246608 KB Output is correct
14 Correct 1867 ms 246564 KB Output is correct
15 Correct 1748 ms 225376 KB Output is correct