結果

問題 No.861 ケーキカット
ユーザー i_mrhji_mrhj
提出日時 2019-09-05 18:03:08
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 1,652 bytes
コンパイル時間 1,890 ms
コンパイル使用メモリ 31,304 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-02 15:22:22
合計ジャッジ時間 3,896 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
4,380 KB
testcase_01 AC 5 ms
4,376 KB
testcase_02 AC 4 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 4 ms
4,376 KB
testcase_05 AC 6 ms
4,380 KB
testcase_06 AC 41 ms
4,376 KB
testcase_07 AC 6 ms
4,380 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 5 ms
4,380 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) > (b) ? (b) : (a))
#define abs(x) ((x) > 0 ? (x) : -(x))
#define MOD (ll)1000000007 //10^9 + 7
#define endl printf("\n")
typedef long long ll;
#define MAX_N (1 << 17)

int d[5][5]; ll c[5][5];

bool
cjudge(int x[5][5])
{
  int s = 0;
  for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
      int z = 0, w = 0;
      for (int p = -1; p <= 1; p++) {
	for (int q = -1; q <= 1; q++) {
	  if(p * q == 0 &&
	     0 <= i + p && i + p < 5 &&
	     0 <= j + q && j + q < 5
	     ) {
	    z++;
	    if (x[i][j] == 1 && x[i + p][j + q] == 0) w++;
	  }
	}
      }
      if (z == w) return false;
    }
  }
  return true;
}

ll sum, ans = LLONG_MAX;

void
dfs(int i, ll r, bool sign)
{
  if (i == 25  || r >= sum / 2) {
    ans = Min(ans, abs(sum - (ll)2 * r));
    return;
  }
  int s = i / 5, t = i % 5;
  if (!sign) {
    d[s][t] = 1;
    dfs(i + 1, r + c[s][t], true);
    d[s][t] = 0;
  } else {
    for (int x = -1; x <= 1; x++) {
      for (int y = -1; y <= 1; y++) {
	if (x * y == 0 &&
	    0 <= s + x && s + x < 5 &&
	    0 <= t + y && t + y < 5 && 
	    d[s + x][t + y] == 1) {
	  d[s][t] = 1;
	  dfs(i + 1, r + c[s][t], true);
	  d[s][t] = 0;
	  break;
	}
      }
    }
    dfs(i + 1, r, true);
  }
  return;
}
    
	  
  
int
main(int argc, char *argv[])
{
  for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
      scanf("%lld", &c[i][j]);
      sum += c[i][j];
    }
  }

  dfs(0, 0, false);

  printf("%lld\n", ans);

  return 0;
}
0