結果

問題 No.45 回転寿司
ユーザー C_kumo
提出日時 2019-01-17 03:46:37
言語 C
(gcc 13.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 1 WA * 29
権限があれば一括ダウンロードができます

ソースコード

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