oj.uz

Submission #595639

# Submission time Handle Problem Language Result Execution time Memory
595639 2022-07-13T22:38:18 Z Bench0310 Quality Of Living (IOI10_quality) C++17
100 / 100
 1641 ms 139996 KB 
#include <bits/stdc++.h>
#include "quality.h"

int rectangle(int n,int m,int h,int w,int a[3001][3001])
{
    int l=0,r=n*m;
    int s[n+1][m+1];
    memset(s,0,sizeof(s));
    while(l<r-1)
    {
        int lim=(l+r)/2;
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(a[i-1][j-1]<=lim);
        bool ok=0;
        for(int i=h;i<=n;i++) for(int j=w;j<=m;j++) ok|=(s[i][j]-s[i-h][j]-s[i][j-w]+s[i-h][j-w]>=(h*w+1)/2);
        if(ok) r=lim;
        else l=lim;
    }
    return r;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 724 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 13 ms 2696 KB Output is correct
8 Correct 16 ms 2620 KB Output is correct
9 Correct 12 ms 2516 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 13 ms 2696 KB Output is correct
8 Correct 16 ms 2620 KB Output is correct
9 Correct 12 ms 2516 KB Output is correct
10 Correct 166 ms 18784 KB Output is correct
11 Correct 186 ms 18852 KB Output is correct
12 Correct 81 ms 11468 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 13 ms 2696 KB Output is correct
8 Correct 16 ms 2620 KB Output is correct
9 Correct 12 ms 2516 KB Output is correct
10 Correct 166 ms 18784 KB Output is correct
11 Correct 186 ms 18852 KB Output is correct
12 Correct 81 ms 11468 KB Output is correct
13 Correct 1641 ms 139996 KB Output is correct
14 Correct 1603 ms 139992 KB Output is correct
15 Correct 1439 ms 129380 KB Output is correct