結果

問題 No.861 ケーキカット
ユーザー 👑 testestest
提出日時 2018-10-23 17:08:04
言語 C
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 872 bytes
コンパイル時間 193 ms
コンパイル使用メモリ 29,952 KB
実行使用メモリ 15,304 KB
最終ジャッジ日時 2024-11-19 04:22:14
合計ジャッジ時間 51,165 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 3
other TLE * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'main':
main.c:31:17: warning: implicit declaration of function 'scanf' [-Wimplicit-function-declaration]
   31 |                 scanf("%ld",&s[i]);
      |                 ^~~~~
main.c:1:1: note: include '<stdio.h>' or provide a declaration of 'scanf'
  +++ |+#include <stdio.h>
    1 | // O(n 2^n)はさすがに通らない（6sくらい）
main.c:31:17: warning: incompatible implicit declaration of built-in function 'scanf' [-Wbuiltin-declaration-mismatch]
   31 |                 scanf("%ld",&s[i]);
      |                 ^~~~~
main.c:31:17: note: include '<stdio.h>' or provide a declaration of 'scanf'
main.c:44:27: warning: implicit declaration of function 'labs' [-Wimplicit-function-declaration]
   44 |                         t=labs(t);
      |                           ^~~~
main.c:1:1: note: include '<stdlib.h>' or provide a declaration of 'labs'
  +++ |+#include <stdlib.h>
    1 | // O(n 2^n)はさすがに通らない（6sくらい）
main.c:44:27: warning: incompatible implicit declaration of built-in function 'labs' [-Wbuiltin-declaration-mismatch]
   44 |                         t=labs(t);
      |                           ^~~~
main.c:44:27: note: include '<stdlib.h>' or provide a declaration of 'labs'
main.c:48:9: warning: implicit declaration of function 'printf' [-Wimplicit-function-declaration]
   48 |         printf("%ld",ans);
      |         ^~~~~~
main.c:48:9: note: include '<stdio.h>' or provide a declaration of 'printf'
main.c:48:9: warning: incompatible implicit declaration of built-in function 'printf' [-Wbuiltin-declaration-mismatch]
main.c:48:9: note: 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