Submission #831798

#	Time	Username	Problem	Language	Result	Execution time	Memory
831798		matthewhutama	Quality Of Living (IOI10_quality)	C++14	100 / 100	2433 ms	175488 KiB

quality

#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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20