Submission #502553

---

Source Code Expand

// {{{ include
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
// }}}

using namespace std;

typedef long long ll;
typedef pair<int, int> duo;
inline int in(){int x;scanf("%d",&x);return x;}
int N, K;

bool inBounds(int sx, int sy, int ex, int ey, const duo& p){
  return sx <= p.first && p.first <= ex && sy <= p.second && p.second <= ey;
}


void rect(const vector<duo>& P, int b, int& x, int& y, int& w, int& h){
  int min_x, min_y, max_x, max_y;
  min_x = min_y = N + 1;
  max_x = max_y = -1;

  for (int i = 0; i < K; i++){
    if ((b >> i) & 1) {
      const duo& p = P[i];
      min_x = min(min_x, p.first);
      min_y = min(min_y, p.second);
      max_x = max(max_x, p.first);
      max_y = max(max_y, p.second);
    }
  }
  x = min_x;
  y = min_y;
  w = max_x - min_x + 1;
  h = max_y - min_y + 1;
}


bool valid(const vector<duo>& P, int b, int x, int y, int w, int h){
  if (x <= 0 || y <= 0 || x + w - 1 > N || y + h - 1 > N) return false;
  for (int i = 0; i < K; i++){
    if ((b >> i) & 1) continue;
    if (inBounds(x, y, x + w - 1, y + h - 1, P[i])) return false;
  }
  return true;
}

int score(const vector<duo>& P, int b, int x, int y, int w, int h){
  if (!valid(P, b, x, y, w, h)) return -1;
  int red = 0;
  int blue = 0;
  if (w % 2 && h % 2) {
    if ((x + y) % 2) blue++;
    else red++;
  }
  for (int i = 0; i < K; i++){
    if (!((b >> i) & 1)) continue;
    const auto& p = P[i];
    if ((p.first + p.second) % 2) red += 2;
    else blue += 2;
  }
  return abs(red - blue);
}

int main()
{
  N = in(), K = in();
  vector<duo> P;
  for (int i = 0; i < K; i++){
    int y = in();
    int x = in();
    P.emplace_back(x, y);
  }

  int maxi = 1;
  for (int b = 1; b < (1 << K); b++){
    int x, y;
    int w, h;
    rect(P, b, x, y, w, h);
    maxi = max({
        score(P, b, x, y, w, h),
        score(P, b, x - 1, y, w + 1, h),
        score(P, b, x, y - 1, w, h + 1),
        score(P, b, x, y, w + 1, h),
        score(P, b, x, y, w, h + 1),
        score(P, b, x - 1, y - 1, w + 1, h + 1),
        score(P, b, x, y, w + 1, h + 1),
        score(P, b, x - 1, y, w + 1, h + 1),
        score(P, b, x, y - 1, w + 1, h + 1),
        maxi
    });
  }
  cout << maxi << endl;

  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int in()’:
./Main.cpp:18:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 inline int in(){int x;scanf("%d",&x);return x;}
                                     ^

Judge Result