結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0