結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
![]() |
提出日時 | 2019-02-13 15:41:20 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 374 ms / 5,000 ms |
コード長 | 3,353 bytes |
コンパイル時間 | 304 ms |
コンパイル使用メモリ | 31,232 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-13 10:02:09 |
合計ジャッジ時間 | 1,517 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#include <float.h>#include <limits.h>#include <math.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <time.h>// 内部定数#define D_ON 1 // 汎用フラグ - ON#define D_OFF 0 // 汎用フラグ - OFF#define D_ITM_MAX 14 // 最大品物数#define D_PTN_MAX 20000 // 最大パターン数// 内部変数static FILE *szpFpI; // 入力static int siICnt; // 品物数static int si2Score[D_ITM_MAX][D_ITM_MAX]; // スコア表static int si1Sum[D_ITM_MAX][D_PTN_MAX]; // 合計得点static int siMax; // 最大得点// 内部変数 - テスト用#ifdef D_TESTstatic int siRes;static FILE *szpFpA;#endif// 合計 - セットintfSetSum(int *pipINo // <I> 品物, int piICnt // <I> 品物数, int piISum // <I> 品物合計, int piSSum // <I> 合計得点){int i, j;// 選択終了if (piICnt >= siICnt) {// 最大得点 - 更新if (siMax < piSSum) {siMax = piSSum;}return 0;}// 合計得点if (piSSum > 0) {if (si1Sum[piICnt][piISum] >= piSSum) {return 0;}si1Sum[piICnt][piISum] = piSSum;}// 品物選択for (i = 0; i < siICnt; i++) {// 選択済if (pipINo[i] == D_ON) {continue;}// 加算得点int liAdd = 0;for (j = 0; j < siICnt; j++) {if (pipINo[j] == D_ON) {liAdd += si2Score[j][i];}}// 品物選択pipINo[i] = D_ON;// 下位へfSetSum(pipINo, piICnt + 1, piISum + (1 << i), piSSum + liAdd);// 品物選択 - キャンセルpipINo[i] = D_OFF;}return 0;}// 実行メインintfMain(int piTNo // <I> テスト番号 1~){int i;char lc1Buf[1024], lc1Out[1024];// データ - 初期化memset(si2Score, 0, sizeof(si2Score)); // スコア表siMax = 0; // 最大得点// 入力 - セット#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// 品物数・スコア数 - 取得int liSCnt;fgets(lc1Buf, sizeof(lc1Buf), szpFpI);sscanf(lc1Buf, "%d%d", &siICnt, &liSCnt);// スコア表 - 取得for (i = 0; i < liSCnt; i++) {int liINo1, liINo2, liScore;fgets(lc1Buf, sizeof(lc1Buf), szpFpI);sscanf(lc1Buf, "%d%d%d", &liINo1, &liINo2, &liScore);// スコア表 - セットsi2Score[liINo1][liINo2] = liScore;}// 合計 - セットint li1Itm[D_ITM_MAX];memset(li1Itm, D_OFF, sizeof(li1Itm));fSetSum(li1Itm, 0, 0, 0);// 結果 - セットsprintf(lc1Out, "%d\n", siMax);// 結果 - 表示#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;}