結果

問題 No.861 ケーキカット
ユーザー testestesttestestest
提出日時 2018-10-23 17:08:04
言語 C
(gcc 12.3.0)
結果
TLE  
実行時間 -
コード長 872 bytes
コンパイル時間 362 ms
コンパイル使用メモリ 29,580 KB
実行使用メモリ 40,112 KB
最終ジャッジ日時 2023-08-12 06:24:25
合計ジャッジ時間 5,249 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: 関数 ‘main’ 内:
main.c:31:17: 警告: 関数 ‘scanf’ の暗黙的な宣言です [-Wimplicit-function-declaration]
   31 |                 scanf("%ld",&s[i]);
      |                 ^~~~~
main.c:1:1: 備考: include ‘<stdio.h>’ or provide a declaration of ‘scanf’
  +++ |+#include <stdio.h>
    1 | // O(n 2^n)はさすがに通らない（6sくらい）
main.c:31:17: 警告: 組み込み関数 ‘scanf’ の互換性がない暗黙的な宣言です [-Wbuiltin-declaration-mismatch]
   31 |                 scanf("%ld",&s[i]);
      |                 ^~~~~
main.c:31:17: 備考: include ‘<stdio.h>’ or provide a declaration of ‘scanf’
main.c:44:27: 警告: 関数 ‘labs’ の暗黙的な宣言です [-Wimplicit-function-declaration]
   44 |                         t=labs(t);
      |                           ^~~~
main.c:1:1: 備考: include ‘<stdlib.h>’ or provide a declaration of ‘labs’
  +++ |+#include <stdlib.h>
    1 | // O(n 2^n)はさすがに通らない（6sくらい）
main.c:44:27: 警告: 組み込み関数 ‘labs’ の互換性がない暗黙的な宣言です [-Wbuiltin-declaration-mismatch]
   44 |                         t=labs(t);
      |                           ^~~~
main.c:44:27: 備考: include ‘<stdlib.h>’ or provide a declaration of ‘labs’
main.c:48:9: 警告: 関数 ‘printf’ の暗黙的な宣言です [-Wimplicit-function-declaration]
   48 |         printf("%ld",ans);
      |         ^~~~~~
main.c:48:9: 備考: include ‘<stdio.h>’ or provide a declaration of ‘printf’
main.c:48:9: 警告: 組み込み関数 ‘printf’ の互換性がない暗黙的な宣言です [-Wbuiltin-declaration-mismatch]
main.c:48:9: 備考: include ‘<stdio.h>’ or provide a declaration of ‘printf’

ソースコード

diff # 

// O(n 2^n)はさすがに通らない（6sくらい）

long s[25];
int board[25];
int cnt1,cnt2;

void dfs(int n){
	cnt2++;
	board[n]+=2;
	if(n%5!=0&&board[n-1]<2&&board[n]%2==board[n-1]%2)dfs(n-1);//左
	if(n%5!=4&&board[n+1]<2&&board[n]%2==board[n+1]%2)dfs(n+1);//右
	if(n>=5&&board[n-5]<2&&board[n]%2==board[n-5]%2)dfs(n-5);//上
	if(n<20&&board[n+5]<2&&board[n]%2==board[n+5]%2)dfs(n+5);//下
}

int f(){
	cnt2=0;
	dfs(0);
	int n=0;
	while(n<25&&board[n]>=2)n++;
	if(n==25)return 1;
	if(cnt2!=cnt1&&cnt2+cnt1!=25)return 0;
	dfs(n);
	return cnt2==25;
}


int main(){
	long ans=0;
	for(int i=0;i<25;i++){
		scanf("%ld",&s[i]);
		ans+=s[i];
	}
	
	for(int n=0;n<1<<25;n++){
		long t=0;
		cnt1=0;
		for(int k=0;k<25;k++){
			board[k]=(n>>k)&1;
			t+=board[k]?s[k]:-s[k];
			if(board[k])cnt1++;
		}
		if(f()){
			t=labs(t);
			if(t<ans)ans=t;
		}
	}
	printf("%ld",ans);
}
0