oj.uz

Submission #831798

# Submission time Handle Problem Language Result Execution time Memory
831798 2023-08-20T15:13:47 Z matthewhutama Quality Of Living (IOI10_quality) C++14
100 / 100
 2433 ms 175488 KB 
#include "quality.h"
#include <bits/stdc++.h>
// #include <stdio.h>
// #include <stdlib.h>
// #include "quality.h"
using namespace std;
typedef long long ll;
int grid[3001][3001];
int pref[3005][3005];
// static int R,C,H,W,Q[3001][3001],i,j,ans;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    int lo = 1, hi = R * C, simpan;
    while (lo <= hi){
        int mid = (lo + hi) / 2;
        memset(pref, 0, sizeof(pref));
        // cout<<mid<<endl;
        for (int i = 1; i <= R; i++){
            for (int j = 1; j <= C; j++){
                if (Q[i - 1][j - 1] == mid){
                    grid[i][j] = 0;
                }
                else if (Q[i - 1][j - 1] > mid){
                    grid[i][j] = 1;
                }
                else{
                    grid[i][j] = -1;
                }
                // cout << grid[i][j]<<" ";
            }
            // cout<<endl;
        }
        // cout<<"_____________________"<<endl;
        for (int i = 1; i <= R; i++){
            for (int j = 1; j <= C; j++){
                if (i == 1 && j == 1){
                    pref[i][j] = grid[i][j];
                    // cout<<pref[i][j]<<" ";
                    continue;
                }
                pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + grid[i][j];
                // cout<<pref[i][j]<<" ";
            }
            // cout<<endl;
        }
        int x = 0;
        for (int i = 1; i <= R - H + 1; i++){
            if (x == 1) break;
            for (int j = 1; j <= C - W + 1; j++){
                int p = i + H - 1, q = j + W - 1;
                int u = pref[p][q] - pref[p][j - 1] - pref[i - 1][q] + pref[i - 1][j - 1];
                if (u <= 0){
                    x = 1;
                    break;
                }
            }
        }
        // cout<<"_______________________"<<endl;

        if (x == 0){
            lo = mid + 1;
        }
        else{
            hi = mid - 1;
            simpan = mid;
        }
    }
    return simpan;
}


// int main(){
//    scanf("%d%d%d%d",&R,&C,&H,&W);
//    for (i=0;i<R;i++) for (j=0;j<C;j++) scanf("%d",&Q[i][j]);
//    ans = rectangle(R,C,H,W,Q);
//    printf("%d\n",ans);
//    return 0;
// }

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35924 KB Output is correct
2 Correct 38 ms 35852 KB Output is correct
3 Correct 38 ms 35796 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35924 KB Output is correct
2 Correct 38 ms 35852 KB Output is correct
3 Correct 38 ms 35796 KB Output is correct
4 Correct 49 ms 36564 KB Output is correct
5 Correct 46 ms 36436 KB Output is correct
6 Correct 50 ms 36564 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35924 KB Output is correct
2 Correct 38 ms 35852 KB Output is correct
3 Correct 38 ms 35796 KB Output is correct
4 Correct 49 ms 36564 KB Output is correct
5 Correct 46 ms 36436 KB Output is correct
6 Correct 50 ms 36564 KB Output is correct
7 Correct 77 ms 39148 KB Output is correct
8 Correct 74 ms 39252 KB Output is correct
9 Correct 72 ms 39136 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35924 KB Output is correct
2 Correct 38 ms 35852 KB Output is correct
3 Correct 38 ms 35796 KB Output is correct
4 Correct 49 ms 36564 KB Output is correct
5 Correct 46 ms 36436 KB Output is correct
6 Correct 50 ms 36564 KB Output is correct
7 Correct 77 ms 39148 KB Output is correct
8 Correct 74 ms 39252 KB Output is correct
9 Correct 72 ms 39136 KB Output is correct
10 Correct 298 ms 58224 KB Output is correct
11 Correct 304 ms 58224 KB Output is correct
12 Correct 177 ms 50788 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35924 KB Output is correct
2 Correct 38 ms 35852 KB Output is correct
3 Correct 38 ms 35796 KB Output is correct
4 Correct 49 ms 36564 KB Output is correct
5 Correct 46 ms 36436 KB Output is correct
6 Correct 50 ms 36564 KB Output is correct
7 Correct 77 ms 39148 KB Output is correct
8 Correct 74 ms 39252 KB Output is correct
9 Correct 72 ms 39136 KB Output is correct
10 Correct 298 ms 58224 KB Output is correct
11 Correct 304 ms 58224 KB Output is correct
12 Correct 177 ms 50788 KB Output is correct
13 Correct 2433 ms 175452 KB Output is correct
14 Correct 2365 ms 175488 KB Output is correct
15 Correct 2191 ms 168468 KB Output is correct