oj.uz

Submission #536310

# Submission time Handle Problem Language Result Execution time Memory
536310 2022-03-12T19:59:19 Z Leo121 Quality Of Living (IOI10_quality) C++14
100 / 100
 1775 ms 141220 KB 
#include <bits/stdc++.h>
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define mp make_pair
#define fi first
#define se second
#include "grader.h"
///#include "quality.h"
using namespace std;
typedef pair<int, int> pii;
const int lim = 3e3;
int pfm[lim + 2][lim + 2];
pii pos[lim * lim + 2];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    forn(i, 0, R - 1){
        forn(j, 0, C - 1){
            pos[Q[i][j]] = mp(i + 1, j + 1);
        }
    }
    int mitadtot = (H * W) / 2;
    int li = 1, ls = R * C, mitad, res;
    bool bandera = 0, bandera1;
    int suma;
    while(li <= ls){
        mitad = (li + ls) / 2;
        forn(i, 0, R - 1){
            forn(j, 0, C - 1){
                pfm[i + 1][j + 1] = (Q[i][j] < mitad) ? 1 : 0;
                pfm[i + 1][j + 1] += pfm[i + 1][j] + pfm[i][j + 1] - pfm[i][j];
            }
        }
        ///cout << mitad << "\n";
        /**forn(i, 1, R){
            forn(j, 1, C){
                ///cout << pfm[i][j] << " ";
            }
            ///cout << "\n";
        }*/
        bandera = 0;
        bandera1 = 0;
        forn(i, H, R){
            forn(j, W, C){
                suma = pfm[i][j] - pfm[i - H][j] - pfm[i][j - W] + pfm[i - H][j - W];
                ///cout << i << " " << j << " " << suma << " ";
                if(suma > mitadtot){
                    bandera1 = 1;
                }
                if(suma == mitadtot){
                    if((pos[mitad].fi > i - H && pos[mitad].fi <= i) && (pos[mitad].se > j - W && pos[mitad].se <= j)){
                        bandera = 1;
                    }
                }
            }
            ///cout << "\n";

        }
        if(bandera1){
            ls = mitad - 1;
        }
        else if(!bandera){
            li = mitad + 1;
        }
        else{
            res = mitad;
            break;
        }
    }
    return res;
}

Compilation message

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

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 2 ms 1264 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 2 ms 1264 KB Output is correct
7 Correct 16 ms 4132 KB Output is correct
8 Correct 14 ms 4132 KB Output is correct
9 Correct 13 ms 3960 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 2 ms 1264 KB Output is correct
7 Correct 16 ms 4132 KB Output is correct
8 Correct 14 ms 4132 KB Output is correct
9 Correct 13 ms 3960 KB Output is correct
10 Correct 178 ms 23972 KB Output is correct
11 Correct 171 ms 23964 KB Output is correct
12 Correct 95 ms 16072 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 2 ms 1264 KB Output is correct
7 Correct 16 ms 4132 KB Output is correct
8 Correct 14 ms 4132 KB Output is correct
9 Correct 13 ms 3960 KB Output is correct
10 Correct 178 ms 23972 KB Output is correct
11 Correct 171 ms 23964 KB Output is correct
12 Correct 95 ms 16072 KB Output is correct
13 Correct 1775 ms 141220 KB Output is correct
14 Correct 1678 ms 141220 KB Output is correct
15 Correct 1542 ms 134136 KB Output is correct