結果
問題 | No.37 遊園地のアトラクション |
ユーザー |
![]() |
提出日時 | 2019-01-24 15:54:53 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 7 ms / 5,000 ms |
コード長 | 4,317 bytes |
コンパイル時間 | 193 ms |
コンパイル使用メモリ | 32,640 KB |
実行使用メモリ | 7,764 KB |
最終ジャッジ日時 | 2024-10-10 13:31:42 |
合計ジャッジ時間 | 1,212 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
#include <limits.h>#include <math.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <time.h>// 内部定数#define D_ATR_MAX 15 * 10 // 最大アトラクション数#define D_TIME_MAX 10000 // 最大滞在時間// 内部構造体 - アトラクション情報typedef struct Atr {int miTime; // 行列時間int miVal; // 満足度} Atr;// 内部変数static FILE *szpFpI; // 入力static int siTime; // 滞在時間static Atr sz1Atr[D_ATR_MAX]; // アトラクションstatic int siACnt; // アトラクション数static int si2Val[D_ATR_MAX][D_TIME_MAX + 5]; // 満足度[アトラクション][滞在時間]// 内部変数 - テスト用#ifdef D_TESTstatic int siRes;static FILE *szpFpA;#endif// ソート関数 - (満足度 / 行列時間) の降順intfSortFnc(const void *pzpVal1 // <I> 値1, const void *pzpVal2 // <I> 値2){Atr *lzpVal1 = (Atr *)pzpVal1;Atr *lzpVal2 = (Atr *)pzpVal2;// 満足度 / 行列時間double ldRate1 = (double)lzpVal1->miVal / (double)lzpVal1->miTime;double ldRate2 = (double)lzpVal2->miVal / (double)lzpVal2->miTime;// (満足度 / 行列時間) の降順if (ldRate1 > ldRate2) {return(-1);}else if (ldRate1 < ldRate2) {return(1);}return 0;}// 満足度 - セットintfSetVal(int piTime // <I> 滞在時間, int piVal // <I> 満足度, int piANo // <I> アトラクション){// 滞在時間 - チェックif (piTime > siTime) {return 0;}// 満足度 - チェック・更新if (piTime > 0) {if (si2Val[piANo][piTime] >= piVal) {return 0;}si2Val[piANo][piTime] = piVal;}// 終了チェックif (piANo >= siACnt) {return 0;}// アトラクション - 使用fSetVal(piTime + sz1Atr[piANo].miTime, piVal + sz1Atr[piANo].miVal, piANo + 1);// アトラクション - 未使用fSetVal(piTime, piVal, piANo + 1);return 0;}// 実行メインintfMain(int piTNo // <I> テスト番号 1~){int i;char lc1Buf[1024], lc1Out[1024];// データ - 初期化memset(si2Val, 0, sizeof(si2Val)); // 満足度[アトラクション][滞在時間]// 入力 - セット#ifdef D_TESTsprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo);szpFpI = fopen(lc1Buf, "r");sprintf(lc1Buf, ".\\Test\\A%d.txt", piTNo);szpFpA = fopen(lc1Buf, "r");siRes = 0;#elseszpFpI = stdin;#endif// 滞在時間 - 取得fgets(lc1Buf, sizeof(lc1Buf), szpFpI);sscanf(lc1Buf, "%d", &siTime);// アトラクション数 - 取得int liACnt;fgets(lc1Buf, sizeof(lc1Buf), szpFpI);sscanf(lc1Buf, "%d", &liACnt);// 行列時間 - 取得for (i = 0; i < liACnt; i++) {fscanf(szpFpI, "%d", &sz1Atr[i].miTime);}fgets(lc1Buf, sizeof(lc1Buf), szpFpI);// 満足度 - 取得for (i = 0; i < liACnt; i++) {fscanf(szpFpI, "%d", &sz1Atr[i].miVal);}fgets(lc1Buf, sizeof(lc1Buf), szpFpI);// アトラクション数siACnt = liACnt;// 2回目以降のアトラクション - 追加for (i = 0; i < liACnt; i++) {int liVal = sz1Atr[i].miVal;while (liVal > 1) {liVal /= 2;sz1Atr[siACnt].miTime = sz1Atr[i].miTime;sz1Atr[siACnt].miVal = liVal;siACnt++;}}// アトラクション - ソートqsort(sz1Atr, siACnt, sizeof(Atr), fSortFnc);// 満足度 - セットfSetVal(0, 0, 0);// 最大満足度 - 取得int liMax = INT_MIN;for (i = 0; i <= siTime; i++) {if (liMax < si2Val[siACnt][i]) {liMax = si2Val[siACnt][i];}}// 結果 - セットsprintf(lc1Out, "%d\n", liMax);// 結果 - 表示#ifdef D_TESTfgets(lc1Buf, sizeof(lc1Buf), szpFpA);if (strcmp(lc1Buf, lc1Out)) {siRes = -1;}#elseprintf("%s", lc1Out);#endif// 残データ有無#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", piTNo);}else {printf("NG %d\n", piTNo);}#endifreturn 0;}intmain(){#ifdef D_TESTint i;for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {fMain(i);}#elsefMain(0);#endifreturn 0;}