結果

問題 No.45 回転寿司
ユーザー C_kumoC_kumo
提出日時 2019-01-17 03:46:37
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 1,909 bytes
コンパイル時間 663 ms
コンパイル使用メモリ 29,824 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-01 06:37:44
合計ジャッジ時間 1,825 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
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 AC 1 ms
6,944 KB
testcase_23 AC 1 ms
6,940 KB
testcase_24 AC 1 ms
6,944 KB
testcase_25 AC 1 ms
6,940 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 AC 1 ms
6,940 KB
testcase_33 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>

void iniScore(short n,char v[],short score[]);
int pickBest(short n,char v[],short score[],short *picked);
void updateScore(short n,char v[],short score[],short picked,short *sushi);

int main(void)
{
	short n,i,picked,sushi;
	char *v;
	short *score;
	int ans;

	scanf("%hd",&n);
	v = (char *)malloc(sizeof(char) * n);
	if (v == NULL) {
		perror("v malloc");
		exit(1);
	}
	for (i=0;i<n;i++) scanf("%hhd",&v[i]);

	score = (short *)malloc(sizeof(short) * n);
	if (score == NULL) {
		perror("score malloc");
		exit(1);
	}

	iniScore(n,v,score);
	ans = 0;
	sushi = n;

	while (1) {
		ans += pickBest(n,v,score,&picked);
		updateScore(n,v,score,picked,&sushi);

		if (sushi <= 0) break;
	}

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

	return 0;
}

void iniScore(short n,char v[],short score[])
{
	short i;

	// head, tail
	score[0] = v[0] - v[1];
	score[n-1] = v[n-1] - v[n-2];

	// others
	for (i=1;i<n-1;i++) {
		score[i] = v[i] - v[i-1] - v[i+1];
	}

	return;
}

int pickBest(short n,char v[],short score[],short *picked)
{
	short i,value,maxSushi,maxScore;
	
	// find max
	maxScore = -999;
	for (i=0;i<n;i++) {
		if (maxScore < score[i]) {
			maxScore = score[i];
			maxSushi = i;
		}
	}
	
	// pick max
	*picked = maxSushi;
	value = v[maxSushi];
	v[maxSushi] = 0;

	return value;
}

void updateScore(short n,char v[],short score[],short picked,short *sushi)
{
	short i,p;

	// oo*oo
	p = picked;
	score[p] = -999;
	*sushi -= 1;
	
	// o*x*o
	p = picked - 1;
	if (p >= 0 || p < n) {
		v[p] = 0;
		score[p] = -999;
		*sushi -= 1;
	}
	p = picked + 1;
	if (p >= 0 || p < n) {
		v[p] = 0;
		score[p] = -999;
		*sushi -= 1;
	}

	// *oxo*
	p = picked - 2;
	if (p > 0) {
		score[p] = v[p] - v[p-1] - v[p+1];
	} else if (p == 0) {
		score[p] = v[p] - v[p+1];
	}
	p = picked + 2;
	if (p < n-1) {
		score[p] = v[p] - v[p-1] - v[p+1];
	} else if (p == n-1) {
		score[p] = v[p] - v[p-1];
	}

	return;
}
0