oj.uz

Submission #399109

# Submission time Handle Problem Language Result Execution time Memory
399109 2021-05-05T10:04:52 Z AugustinasJucas Quality Of Living (IOI10_quality) C++14
100 / 100
 1591 ms 175392 KB 
#include "quality.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int dydis = 3e3 +  1;
int mas[dydis][dydis];
int n, m, w, h;
int pref[dydis][dydis];
int sm(int e1, int s1, int e2, int s2){
    int vk = 0, vd = 0, ak = 0, ad = 0;
    if(e1 != 0 && s1 != 0) vk = pref[e1-1][s1-1];
    if(e1 != 0) vd = pref[e1-1][s2];
    if(s1 != 0) ak = pref[e2][s1-1];
    ad = pref[e2][s2];
    return ad - vd - ak + vk;
}
bool f(int x){
    for(int i = 0; i < n; i++){
        int sm = 0;
        for(int j = 0; j < m; j++){
            sm += mas[i][j] <= x;
            pref[i][j] = (i == 0 ? 0 : pref[i-1][j]) + sm;
        }
    }

    for(int i = 0; i <= n-h; i++){
        for(int j = 0; j <= m-w; j++){
            if(sm(i, j, i+h-1, j+w-1) >= w * h / 2 + 1) return true;
        }
    }
    return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	n = R, m = C, w = W, h = H;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) mas[i][j] = Q[i][j];
     int l = 1; int r = n * m;

    int ans = 1e9;
    while(l <= r){
        int mid = (l + r) / 2;
        if(f(mid)){
            r = mid-1;
            ans = min(ans, mid);
        }else{
            l = mid+1;
        }
    } 
    return ans;

}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1596 KB Output is correct
6 Correct 2 ms 1612 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1596 KB Output is correct
6 Correct 2 ms 1612 KB Output is correct
7 Correct 16 ms 5500 KB Output is correct
8 Correct 14 ms 5416 KB Output is correct
9 Correct 17 ms 5312 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1596 KB Output is correct
6 Correct 2 ms 1612 KB Output is correct
7 Correct 16 ms 5500 KB Output is correct
8 Correct 14 ms 5416 KB Output is correct
9 Correct 17 ms 5312 KB Output is correct
10 Correct 176 ms 30720 KB Output is correct
11 Correct 169 ms 30876 KB Output is correct
12 Correct 87 ms 21368 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1596 KB Output is correct
6 Correct 2 ms 1612 KB Output is correct
7 Correct 16 ms 5500 KB Output is correct
8 Correct 14 ms 5416 KB Output is correct
9 Correct 17 ms 5312 KB Output is correct
10 Correct 176 ms 30720 KB Output is correct
11 Correct 169 ms 30876 KB Output is correct
12 Correct 87 ms 21368 KB Output is correct
13 Correct 1591 ms 175380 KB Output is correct
14 Correct 1434 ms 175392 KB Output is correct
15 Correct 1397 ms 168264 KB Output is correct