oj.uz

Submission #591682

# Submission time Handle Problem Language Result Execution time Memory
591682 2022-07-07T18:24:04 Z ogibogi2004 Quality Of Living (IOI10_quality) C++14
100 / 100
 1795 ms 210664 KB 
#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3001;
int table[MAXN][MAXN];
int t1[MAXN][MAXN];
int h,w,r,c;
char dirs[3*MAXN];
int pref[MAXN][MAXN];
bool check(int val)
{
    for(int i=0;i<r;++i)
    {
        for(int j=0;j<c;++j)
        {
            if(table[i][j]<=val)t1[i][j]=1;
            else t1[i][j]=0;
        }
    }
    pref[0][0]=t1[0][0];
    for(int i=1;i<r;i++)pref[i][0]=pref[i-1][0]+t1[i][0];
    for(int i=1;i<c;i++)pref[0][i]=pref[0][i-1]+t1[0][i];
    for(int i=1;i<r;i++)
    {
        for(int j=1;j<c;j++)
        {
            pref[i][j]=t1[i][j]+pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
        }
    }
    for(int i=0;i<=r-h;i++)
    {
        for(int j=0;j<=c-w;j++)
        {
            int cnt=pref[i+h-1][j+w-1];
            if(i!=0)cnt-=pref[i-1][j+w-1];
            if(j!=0)cnt-=pref[i+h-1][j-1];
            if(i!=0&&j!=0)cnt+=pref[i-1][j-1];
            if(cnt>h*w/2)return 1;
        }
    }


    return 0;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    r=R;c=C;h=H;w=W;
    for(int j=0;j<c-w;j++)dirs[j]='R';
    dirs[c-w]='D';
    for(int j=c-w+1;j<(c-w+1)+c-w;j++)dirs[j]='L';
    dirs[(c-w+1)+c-w]='D';
    for(int i=0;i<R;++i)
    {
        for(int j=0;j<C;++j)
        {
            table[i][j]=Q[i][j];
        }
    }
    int low=1,high=R*C,mid,best;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(check(mid))
        {
            best=mid;
            high=mid-1;
        }
        else low=mid+1;
    }
    return best;

}

Compilation message

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:69:12: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |     return best;
      |            ^~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 2 ms 2004 KB Output is correct
5 Correct 2 ms 2004 KB Output is correct
6 Correct 2 ms 2004 KB Output is correct
7 Correct 16 ms 6552 KB Output is correct
8 Correct 16 ms 6484 KB Output is correct
9 Correct 14 ms 6356 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 2 ms 2004 KB Output is correct
5 Correct 2 ms 2004 KB Output is correct
6 Correct 2 ms 2004 KB Output is correct
7 Correct 16 ms 6552 KB Output is correct
8 Correct 16 ms 6484 KB Output is correct
9 Correct 14 ms 6356 KB Output is correct
10 Correct 193 ms 32016 KB Output is correct
11 Correct 187 ms 38748 KB Output is correct
12 Correct 99 ms 27444 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 2 ms 2004 KB Output is correct
5 Correct 2 ms 2004 KB Output is correct
6 Correct 2 ms 2004 KB Output is correct
7 Correct 16 ms 6552 KB Output is correct
8 Correct 16 ms 6484 KB Output is correct
9 Correct 14 ms 6356 KB Output is correct
10 Correct 193 ms 32016 KB Output is correct
11 Correct 187 ms 38748 KB Output is correct
12 Correct 99 ms 27444 KB Output is correct
13 Correct 1795 ms 210624 KB Output is correct
14 Correct 1718 ms 210664 KB Output is correct
15 Correct 1661 ms 203500 KB Output is correct