結果
問題 | No.1792 科学の甲子園 |
ユーザー |
![]() |
提出日時 | 2021-12-24 14:13:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 4,000 ms |
コード長 | 1,398 bytes |
コンパイル時間 | 487 ms |
コンパイル使用メモリ | 44,928 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-26 17:56:35 |
合計ジャッジ時間 | 1,371 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
/* -*- coding: utf-8 -*- * * 1792.cc: No.1792 科学の甲子園 - yukicoder */ #include<cstdio> #include<cstring> #include<algorithm> using namespace std; /* constant */ const int MAX_N = 10000; const int M = 6; const int MBITS = 1 << M; const int MMSK = MBITS - 1; const int K = 4; /* typedef */ typedef long long ll; /* global variables */ int ps[MAX_N][M]; ll sps[MBITS], dp[2][K + 1][MBITS]; /* subroutines */ inline void setmax(ll &a, ll b) { if (a < b) a = b; } /* main */ int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) for (int j = 0; j < M; j++) scanf("%d", ps[i] + j); dp[0][0][0] = 1; int cur = 0, nxt = 1; for (int i = 0; i < n; i++) { for (int bits = 0; bits < MBITS; bits++) { ll mp = 1; for (int j = 0, bj = 1; j < M; j++, bj <<= 1) if (bits & bj) mp *= ps[i][j]; sps[bits] = mp; } memset(dp[nxt], 0, sizeof(dp[nxt])); for (int k = 0; k <= K; k++) for (int bits = 0; bits < MBITS; bits++) if (dp[cur][k][bits] > 0) { setmax(dp[nxt][k][bits], dp[cur][k][bits]); if (k < K) for (int bits1 = 1; bits1 < MBITS; bits1++) if (! (bits & bits1)) setmax(dp[nxt][k + 1][bits | bits1], dp[cur][k][bits] * sps[bits1]); } swap(cur, nxt); } ll maxd = 0; for (int k = 0; k <= K; k++) setmax(maxd, dp[cur][k][MMSK]); printf("%lld\n", maxd); return 0; }