oj.uz

Submission #544525

# Submission time Handle Problem Language Result Execution time Memory
544525 2022-04-02T08:30:52 Z cig32 Quality Of Living (IOI10_quality) C++17
100 / 100
 2307 ms 139968 KB 
#include <stdio.h>
#include <stdlib.h>
#include "bits/stdc++.h"
using namespace std;
#include "quality.h"

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 rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int lb = 1, rb = R * C;
  while(lb<rb) {
    int mid = (lb+rb) >> 1;
    int ps[R][C];
    for(int i=0; i<R; i++) {
      for(int j=0; j<C; j++) {
        ps[i][j] = 0;
        if(i > 0) ps[i][j] += ps[i-1][j];
        if(j > 0) ps[i][j] += ps[i][j-1];
        if(i && j) ps[i][j] -= ps[i-1][j-1];
        if(Q[i][j] <= mid) ps[i][j]++;
      }
    }
    bool ok = 0;
    for(int i=H-1; i<R; i++) {
      for(int j=W-1; j<C; j++) {
        if(ps[i][j] - (i==H-1? 0: ps[i-H][j]) - (j==W-1? 0: ps[i][j-W]) + (i==H-1||j==W-1? 0: ps[i-H][j-W]) >= (H*W+1) / 2) {
          ok = 1;
        }
      }
    }
    if(ok) rb = mid;
    else lb = mid + 1;
  }
  return lb;
}

Compilation message

quality.cpp:7:38: warning: 'ans' defined but not used [-Wunused-variable]
    7 | static int R,C,H,W,Q[3001][3001],i,j,ans;
      |                                      ^~~
quality.cpp:7:36: warning: 'j' defined but not used [-Wunused-variable]
    7 | static int R,C,H,W,Q[3001][3001],i,j,ans;
      |                                    ^
quality.cpp:7:34: warning: 'i' defined but not used [-Wunused-variable]
    7 | static int R,C,H,W,Q[3001][3001],i,j,ans;
      |                                  ^
quality.cpp:7:20: warning: 'Q' defined but not used [-Wunused-variable]
    7 | static int R,C,H,W,Q[3001][3001],i,j,ans;
      |                    ^
quality.cpp:7:18: warning: 'W' defined but not used [-Wunused-variable]
    7 | static int R,C,H,W,Q[3001][3001],i,j,ans;
      |                  ^
quality.cpp:7:16: warning: 'H' defined but not used [-Wunused-variable]
    7 | static int R,C,H,W,Q[3001][3001],i,j,ans;
      |                ^
quality.cpp:7:14: warning: 'C' defined but not used [-Wunused-variable]
    7 | static int R,C,H,W,Q[3001][3001],i,j,ans;
      |              ^
quality.cpp:7:12: warning: 'R' defined but not used [-Wunused-variable]
    7 | static int R,C,H,W,Q[3001][3001],i,j,ans;
      |            ^

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 704 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 704 KB Output is correct
7 Correct 17 ms 2692 KB Output is correct
8 Correct 16 ms 2696 KB Output is correct
9 Correct 16 ms 2516 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 704 KB Output is correct
7 Correct 17 ms 2692 KB Output is correct
8 Correct 16 ms 2696 KB Output is correct
9 Correct 16 ms 2516 KB Output is correct
10 Correct 229 ms 18856 KB Output is correct
11 Correct 219 ms 18856 KB Output is correct
12 Correct 114 ms 11508 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 704 KB Output is correct
7 Correct 17 ms 2692 KB Output is correct
8 Correct 16 ms 2696 KB Output is correct
9 Correct 16 ms 2516 KB Output is correct
10 Correct 229 ms 18856 KB Output is correct
11 Correct 219 ms 18856 KB Output is correct
12 Correct 114 ms 11508 KB Output is correct
13 Correct 2307 ms 139968 KB Output is correct
14 Correct 2239 ms 139968 KB Output is correct
15 Correct 2009 ms 129456 KB Output is correct