Submission #544525

#	Time	Username	Problem	Language	Result	Execution time	Memory
544525		cig32	Quality Of Living (IOI10_quality)	C++17	100 / 100	2307 ms	139968 KiB

quality

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

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