oj.uz

Submission #303053

# Submission time Handle Problem Language Result Execution time Memory
303053 2020-09-19T19:48:30 Z iliccmarko Quality Of Living (IOI10_quality) C++14
100 / 100
 4692 ms 109868 KB 
#include <bits/stdc++.h>
#include<quality.h>
using namespace std;
#define ll long long
#define endl "\n"

using namespace std;

int rectangle(int r, int c, int h, int w, int q[3001][3001])
{
    int l = 1;
    int R = r*c;
    int ans;
    int prefix[r][c];
    while(l<=R)
    {
        int mid = (l+R)/2;
        for(int i = 0;i<r;i++)
        {
            for(int j = 0;j<c;j++)
            {
                if(j==0)
                {
                    if(q[i][j]<mid)
                        prefix[i][j] = -1;
                    else if(q[i][j]==mid)
                        prefix[i][j] = 0;
                    else 
                        prefix[i][j] = 1;
                }
                else
                {
                    if(q[i][j]<mid)
                        prefix[i][j] = -1;
                    else if(q[i][j]==mid)
                        prefix[i][j] = 0;
                    else 
                        prefix[i][j] = 1;
                    prefix[i][j] += prefix[i][j-1];
                }
            }
        }
        int s, e;
        s = e = 0;
        int sum = 0;
        for(int i = w-1;i<c;i++)
        {
            sum = 0;
            for(int j = 0;j<h;j++)
            {
                if(i==w-1)
                {
                    sum+=prefix[j][w-1];
                }
                else
                {
                    sum+=prefix[j][i] - prefix[j][i-w];
                }
            }
            if(sum<0)
            {
                s++;
                break;
            }
            else if(sum==0)
            {
                e++;
            }
            for(int j = h;j<r;j++)
            {
                if(i==w-1)
                {
                    sum-=prefix[j-h][w-1];
                    sum+=prefix[j][w-1];
                }
                else
                {
                    sum-=prefix[j-h][i] - prefix[j-h][i-w];
                    sum+=prefix[j][i] - prefix[j][i-w];
                }
                if(sum<0)
                {
                    s++;
                    break;
                }
                else if(sum==0)
                {
                    e++;
                }
            }
            if(s!=0) break;
        }
        if(s)
        {
            R = mid - 1;
        }
        else if(e)
        {
            ans = mid;
            break;
        }
        else
        {
            l = mid + 1;
        }
    }
    return ans;
}

Compilation message

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

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 26 ms 2176 KB Output is correct
8 Correct 23 ms 2176 KB Output is correct
9 Correct 23 ms 2176 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 26 ms 2176 KB Output is correct
8 Correct 23 ms 2176 KB Output is correct
9 Correct 23 ms 2176 KB Output is correct
10 Correct 302 ms 12152 KB Output is correct
11 Correct 304 ms 12108 KB Output is correct
12 Correct 154 ms 8184 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 26 ms 2176 KB Output is correct
8 Correct 23 ms 2176 KB Output is correct
9 Correct 23 ms 2176 KB Output is correct
10 Correct 302 ms 12152 KB Output is correct
11 Correct 304 ms 12108 KB Output is correct
12 Correct 154 ms 8184 KB Output is correct
13 Correct 4692 ms 71188 KB Output is correct
14 Correct 2948 ms 109868 KB Output is correct
15 Correct 4172 ms 101352 KB Output is correct