結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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_TESTstatic int siRes;static FILE *szpFpA;static int siTNo;#endif// 出力intfOut(char *pcpLine // <I> 1行){char lc1Buf[1024];#ifdef D_TESTfgets(lc1Buf, sizeof(lc1Buf), szpFpA);if (strcmp(lc1Buf, pcpLine)) {siRes = -1;}#elseprintf("%s", pcpLine);#endifreturn 0;}// セグメントツリー - 子の開始位置 - セットintfSegTSetCSNo(int piCnt // <I> 子データ数){siSCNo = 1;while (siSCNo < piCnt) {siSCNo *= 2;}return 0;}// セグメントツリー - 子の処理intfSegTCProc(int piNo1 // <I> 位置1 0~, int piNo2 // <I> 位置2 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;}// セグメントツリー - 親データセットintfSegTSetPData(){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;}// セグメントツリー - 取得intfSegTGetRngMain(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;}intfSegTGetRng(int piGetS // <I> 取得範囲 - 開始 0~, int piGetE // <I> 取得範囲 - 終了 0~){if (piGetE >= siDCnt) {piGetE = siDCnt - 1;}return fSegTGetRngMain(piGetS, piGetE, 1, 0, siSCNo - 1);}// 実行メインintfMain(){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;}// 1回実行intfOne(){int liRet;char lc1Buf[1024];// データ - 初期化memset(sz1SegT, 0, sizeof(sz1SegT)); // セグメントツリー// 入力 - セット#ifdef D_TESTsprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);szpFpI = fopen(lc1Buf, "r");sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);szpFpA = fopen(lc1Buf, "r");siRes = 0;#elseszpFpI = stdin;#endif// 実行メインliRet = fMain();// 残データ有無#ifdef D_TESTlc1Buf[0] = '\0';fgets(lc1Buf, sizeof(lc1Buf), szpFpA);if (strcmp(lc1Buf, "")) {siRes = -1;}#endif// テストファイルクローズ#ifdef D_TESTfclose(szpFpI);fclose(szpFpA);#endif// テスト結果#ifdef D_TESTif (siRes == 0) {printf("OK %d\n", siTNo);}else {printf("NG %d\n", siTNo);}#endifreturn 0;}// プログラム開始intmain(){#ifdef D_TESTint i;for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {siTNo = i;fOne();}#elsefOne();#endifreturn 0;}