oj.uz

Submission #591678

# Submission time Handle Problem Language Result Execution time Memory
591678 2022-07-07T18:18:17 Z ogibogi2004 Quality Of Living (IOI10_quality) C++14
60 / 100
 5000 ms 51420 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];
bool check(int val)
{
    for(int i=0;i<MAXN;++i)
    {
        for(int j=0;j<MAXN;++j)
        {
            if(table[i][j]<=val)t1[i][j]=1;
            else t1[i][j]=0;
        }
    }
    int cnt=0;
    for(int i=0;i<h;++i)
    {
        for(int j=0;j<w;++j)
        {
            if(t1[i][j])++cnt;
        }
    }

    if(cnt>h*w/2)return 1;
    int x=0,y=0,idx=0;
    while(x!=r-h||y!=c-w)
    {
        idx%=2*(c-w+1);
        char dir=dirs[idx];
        if(dir=='R')
        {
            for(int i=x;i<x+h;++i)
            {
                if(t1[i][y]==1)--cnt;
                if(t1[i][y+w]==1)++cnt;
            }
            ++y;
        }
        else if(dir=='L')
        {
            for(int i=x;i<x+h;++i)
            {
                if(t1[i][y+w-1]==1)--cnt;
                if(t1[i][y-1]==1)++cnt;
            }
            --y;
        }
        else if(dir=='D')
        {
            for(int j=y;j<y+w;++j)
            {
                if(t1[x][j]==1)--cnt;
                if(t1[x+h][j]==1)++cnt;
            }
            ++x;
        }
        if(cnt>h*w/2)return 1;
        idx++;
    }
    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:91:12: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |     return best;
      |            ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 35960 KB Output is correct
2 Correct 85 ms 35844 KB Output is correct
3 Correct 86 ms 35808 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 35960 KB Output is correct
2 Correct 85 ms 35844 KB Output is correct
3 Correct 86 ms 35808 KB Output is correct
4 Correct 121 ms 36436 KB Output is correct
5 Correct 112 ms 36464 KB Output is correct
6 Correct 119 ms 36484 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 35960 KB Output is correct
2 Correct 85 ms 35844 KB Output is correct
3 Correct 86 ms 35808 KB Output is correct
4 Correct 121 ms 36436 KB Output is correct
5 Correct 112 ms 36464 KB Output is correct
6 Correct 119 ms 36484 KB Output is correct
7 Correct 328 ms 38716 KB Output is correct
8 Correct 158 ms 38688 KB Output is correct
9 Correct 300 ms 38640 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 35960 KB Output is correct
2 Correct 85 ms 35844 KB Output is correct
3 Correct 86 ms 35808 KB Output is correct
4 Correct 121 ms 36436 KB Output is correct
5 Correct 112 ms 36464 KB Output is correct
6 Correct 119 ms 36484 KB Output is correct
7 Correct 328 ms 38716 KB Output is correct
8 Correct 158 ms 38688 KB Output is correct
9 Correct 300 ms 38640 KB Output is correct
10 Execution timed out 5054 ms 51420 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 35960 KB Output is correct
2 Correct 85 ms 35844 KB Output is correct
3 Correct 86 ms 35808 KB Output is correct
4 Correct 121 ms 36436 KB Output is correct
5 Correct 112 ms 36464 KB Output is correct
6 Correct 119 ms 36484 KB Output is correct
7 Correct 328 ms 38716 KB Output is correct
8 Correct 158 ms 38688 KB Output is correct
9 Correct 300 ms 38640 KB Output is correct
10 Execution timed out 5054 ms 51420 KB Time limit exceeded
11 Halted 0 ms 0 KB -