oj.uz

Submission #582730

# Submission time Handle Problem Language Result Execution time Memory
582730 2022-06-24T11:03:55 Z Dan4Life Quality Of Living (IOI10_quality) C++17
100 / 100
 1746 ms 175284 KB 
#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int n, m, h, w, a[3001][3001], pre[3002][3002];

inline int sum(int x1, int y1, int x2, int y2){
    return pre[x2][y2]-pre[x1-1][y2]-pre[x2][y1-1]+pre[x1-1][y1-1];
}

bool chk(int x){
    for(int i = 0; i <= n; i++) pre[i][0]=0;
    for(int i = 0; i <= m; i++) pre[0][i]=0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            pre[i][j] = pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+(a[i][j]<=x);
    for(int i = 1; i <= n-h+1; i++)
        for(int j = 1; j <= m-w+1; j++)
            if(sum(i,j,i+h-1,j+w-1)>=h*w/2+1) return true;
    return false;
}

int rectangle(int R, int C, int H, int W, int A[3001][3001]) {
    n=R, m=C, h=H, w=W;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            a[i+1][j+1] = A[i][j];
    int l = 0, r = n*m;
    while(l+1<r){
        int mid = (l+r)/2;
        if(chk(mid)) r=mid;
        else l=mid;
    }
    return r;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 1596 KB Output is correct
5 Correct 2 ms 1620 KB Output is correct
6 Correct 2 ms 1600 KB Output is correct
7 Correct 16 ms 5580 KB Output is correct
8 Correct 15 ms 5484 KB Output is correct
9 Correct 18 ms 5336 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 1596 KB Output is correct
5 Correct 2 ms 1620 KB Output is correct
6 Correct 2 ms 1600 KB Output is correct
7 Correct 16 ms 5580 KB Output is correct
8 Correct 15 ms 5484 KB Output is correct
9 Correct 18 ms 5336 KB Output is correct
10 Correct 200 ms 30768 KB Output is correct
11 Correct 178 ms 30796 KB Output is correct
12 Correct 94 ms 21596 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 1596 KB Output is correct
5 Correct 2 ms 1620 KB Output is correct
6 Correct 2 ms 1600 KB Output is correct
7 Correct 16 ms 5580 KB Output is correct
8 Correct 15 ms 5484 KB Output is correct
9 Correct 18 ms 5336 KB Output is correct
10 Correct 200 ms 30768 KB Output is correct
11 Correct 178 ms 30796 KB Output is correct
12 Correct 94 ms 21596 KB Output is correct
13 Correct 1746 ms 175284 KB Output is correct
14 Correct 1713 ms 172876 KB Output is correct
15 Correct 1636 ms 165704 KB Output is correct