結果

問題 No.489 株に挑戦
コンテスト
ユーザー asugen0402
提出日時 2019-04-11 16:34:08
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 38 ms / 1,000 ms
コード長 5,391 bytes
コンパイル時間 1,257 ms
コンパイル使用メモリ 32,640 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-20 00:13:41
合計ジャッジ時間 1,869 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_SEGT_CNT		131072									// セグメントツリーデータ数(2の累乗)

// 内部構造体 - セグメントツリー情報
typedef struct SegT {
	int miVal;													// 価格
	int miDay;													// 日付 0～
} SegT;

// 内部変数
static FILE *szpFpI;											// 入力
static int siDCnt;												// 日数
static int siDLen;												// 期間
static long long slSCnt;										// 株数
static SegT sz1SegT[D_SEGT_CNT * 2];							// セグメントツリー
static int siSCNo;												// セグメントツリー - 子の開始位置

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// 出力
int
fOut(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// セグメントツリー - 子の開始位置 - セット
int
fSegTSetCSNo(
	int piCnt					// <I> 子データ数
)
{
	siSCNo = 1;
	while (siSCNo < piCnt) {
		siSCNo *= 2;
	}

	return 0;
}

// セグメントツリー - 子の処理
int
fSegTCProc(
	int piNo1					// <I> 位置１ 0～
	, int piNo2					// <I> 位置２ 0～
)
{
	// 価格
	if (sz1SegT[piNo1].miVal > sz1SegT[piNo2].miVal) {
		return piNo1;
	}
	else if (sz1SegT[piNo1].miVal < sz1SegT[piNo2].miVal) {
		return piNo2;
	}

	// 日付
	if (sz1SegT[piNo1].miDay < sz1SegT[piNo2].miDay) {
		return piNo1;
	}
	else if (sz1SegT[piNo1].miDay > sz1SegT[piNo2].miDay) {
		return piNo2;
	}

	return piNo1;
}

// セグメントツリー - 親データセット
int
fSegTSetPData(
)
{
	int i;

	// 最初の親番号範囲
	int liPNo1 = siSCNo / 2;
	int liPNo2 = siSCNo - 1;

	// 作成
	while (liPNo1 > 0) {
		for (i = liPNo1; i <= liPNo2; i++) {

			// 対象の子を取得
			int liCNo = fSegTCProc(i * 2, i * 2 + 1);

			// セット
			sz1SegT[i] = sz1SegT[liCNo];
		}

		// 次の親番号範囲
		liPNo2 = liPNo1 - 1;
		liPNo1 /= 2;
	}

	return 0;
}

// セグメントツリー - 取得
int
fSegTGetRngMain(
	int piGetS					// <I> 取得範囲 - 開始 0～
	, int piGetE				// <I> 取得範囲 - 終了 0～
	, int piNNo					// <I> 現在位置 1～
	, int piNowS				// <I> 現在範囲 - 開始 0～
	, int piNowE				// <I> 現在範囲 - 終了 0～
)
{
	// 内包チェック
	if (piGetS <= piNowS && piNowE <= piGetE) {
		return piNNo;
	}

	// 中間位置
	int liCenter = (piNowS + piNowE) / 2;

	int liCNo = -1;

	// 左側
	if (piGetS <= liCenter) {
		liCNo = fSegTGetRngMain(piGetS, piGetE, piNNo * 2, piNowS, liCenter);
	}

	// 右側
	if (piGetE >= liCenter + 1) {
		int liCNo2 = fSegTGetRngMain(piGetS, piGetE, piNNo * 2 + 1, liCenter + 1, piNowE);
		if (liCNo2 >= 0) {
			if (liCNo < 0) {
				liCNo = liCNo2;
			}
			else {
				liCNo = fSegTCProc(liCNo, liCNo2);
			}
		}
	}

	return liCNo;
}
int
fSegTGetRng(
	int piGetS					// <I> 取得範囲 - 開始 0～
	, int piGetE				// <I> 取得範囲 - 終了 0～
)
{
	if (piGetE >= siDCnt) {
		piGetE = siDCnt - 1;
	}

	return fSegTGetRngMain(piGetS, piGetE, 1, 0, siSCNo - 1);
}

// 実行メイン
int
fMain(
)
{
	int i;
	char lc1Buf[1024];

	// 日数・期間・株数 - 取得
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d%lld", &siDCnt, &siDLen, &slSCnt);

	// セグメントツリー - 子の開始位置 - セット
	fSegTSetCSNo(siDCnt);

	// 価格 - 取得
	for (i = 0; i < siDCnt; i++) {
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		sscanf(lc1Buf, "%d", &sz1SegT[siSCNo + i].miVal);
		sz1SegT[siSCNo + i].miDay = i;
	}

	// セグメントツリー - 親データセット
	fSegTSetPData();

	// 最大値 - 取得
	long long llMax = 0;
	int liDSNo = -1;
	int liDENo = -1;
	for (i = 0; i < siDCnt - 1; i++) {
		int liSNo = fSegTGetRng(i + 1, i + siDLen);
		long long llUp = sz1SegT[liSNo].miVal - sz1SegT[siSCNo + i].miVal;
		if (llUp > 0) {
			long long llVal = llUp * slSCnt;
			if (llMax < llVal) {
				llMax = llVal;
				liDSNo = i;
				liDENo = sz1SegT[liSNo].miDay;
			}
		}
	}

	// 出力 - 最大値
	sprintf(lc1Buf, "%lld\n", llMax);
	fOut(lc1Buf);

	// 出力 - 日付
	if (llMax > 0) {
		sprintf(lc1Buf, "%d %d\n", liDSNo, liDENo);
		fOut(lc1Buf);
	}

	return 0;
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// データ - 初期化
	memset(sz1SegT, 0, sizeof(sz1SegT));						// セグメントツリー

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	liRet = fMain();

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}
0