oj.uz

Submission #536309

# Submission time Handle Problem Language Result Execution time Memory
536309 2022-03-12T19:56:50 Z Leo121 Quality Of Living (IOI10_quality) C++14
100 / 100
 1842 ms 210684 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 st[lim * lim * 4 + 2];
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:68:12: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |     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 1 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 1 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 1236 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 1 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 1236 KB Output is correct
7 Correct 23 ms 4084 KB Output is correct
8 Correct 13 ms 4052 KB Output is correct
9 Correct 13 ms 3924 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 1 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 1236 KB Output is correct
7 Correct 23 ms 4084 KB Output is correct
8 Correct 13 ms 4052 KB Output is correct
9 Correct 13 ms 3924 KB Output is correct
10 Correct 175 ms 23944 KB Output is correct
11 Correct 185 ms 30708 KB Output is correct
12 Correct 89 ms 19436 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 1 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 1236 KB Output is correct
7 Correct 23 ms 4084 KB Output is correct
8 Correct 13 ms 4052 KB Output is correct
9 Correct 13 ms 3924 KB Output is correct
10 Correct 175 ms 23944 KB Output is correct
11 Correct 185 ms 30708 KB Output is correct
12 Correct 89 ms 19436 KB Output is correct
13 Correct 1842 ms 210684 KB Output is correct
14 Correct 1710 ms 210608 KB Output is correct
15 Correct 1615 ms 196584 KB Output is correct