Submission #811770


Source Code Expand

Copy
/*
atcoder 柱柱柱柱柱
柱の高さがN個与えられる。柱から右に1つまたは2つ移動できるが、移動するたび柱の高さの差の絶対値だけコストがかかる。
N番目の柱に移動するときにかかる最小のコストを求める.
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/*現在地からの移動コストを求める*/
int getCost(const int* poleheight, int curposition, int nmove){
	return abs(poleheight[curposition]-poleheight[curposition+nmove]);
}

/*動的計画法が使えるのでk番目の柱に到達するのに必要なコストを逐次的に計算して求める.*/
int main()
{
	int *poleheight;	//柱の高さ
	int *polecost;	//柱到達にかかるコスト
	int npole;			//柱の数
	int i;
	int ncost1, ncost2;	//1進む、2進むのに必要なコスト
	//柱の数を入力から受け取り、必要な配列(コストと高さ)を確保する
	scanf("%d", &npole);
	poleheight = (int*)malloc(sizeof(int)*npole);
	polecost = (int*)malloc(sizeof(int)*npole);
	//柱の高さを標準入力から受け取る
	for(i=0;i<npole;i++)scanf("%d", &poleheight[i]);
	//初期条件として0番目と1番目の最小コストは確定
	polecost[0] = 0;
	polecost[1] = getCost(poleheight, 0, 1);
	//探索していきi番目の柱到達までの最小コストを求めていく
	for(i=0;i<npole-2;i++){
		//現在地からの移動コストを取得
		ncost1 = getCost(poleheight, i, 1);
		ncost2 = getCost(poleheight, i, 2);
		//この時点でi番目以前の値は確定、i+2番目以降は未決定
		//i+1番目は一つ前からの合計移動コストと今入っている値を比較して小さい方に確定
		if(polecost[i+1]>(ncost1+polecost[i]))polecost[i+1]=ncost1+polecost[i];
		polecost[i+2]=ncost2;
	}
	printf("%d\n", npole);
	free(polecost);
	free(poleheight);
}




Submission Info

Submission Time
Task C - 柱柱柱柱柱
User sqrt36
Language C (GCC 5.4.1)
Score 0
Code Size 1915 Byte
Status WA
Exec Time 22 ms
Memory 896 KB

Compile Error

./Main.c: In function ‘main’:
./Main.c:23:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &npole);
  ^
./Main.c:27:22: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  for(i=0;i<npole;i++)scanf("%d", &poleheight[i]);
                      ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
WA × 3
WA × 10
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt
Case Name Status Exec Time Memory
sample_01.txt WA 2 ms 128 KB
sample_02.txt WA 2 ms 128 KB
sample_03.txt WA 2 ms 128 KB
subtask1_01.txt WA 2 ms 128 KB
subtask1_02.txt WA 2 ms 128 KB
subtask1_03.txt WA 2 ms 128 KB
subtask1_04.txt WA 22 ms 896 KB
subtask1_05.txt WA 21 ms 896 KB
subtask1_06.txt WA 21 ms 896 KB
subtask1_07.txt WA 21 ms 896 KB