結果
問題 | No.861 ケーキカット |
ユーザー |
|
提出日時 | 2021-03-25 21:20:50 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,128 bytes |
コンパイル時間 | 9,610 ms |
コンパイル使用メモリ | 253,584 KB |
最終ジャッジ日時 | 2025-01-19 21:44:47 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | TLE * 3 |
other | TLE * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long INF = 1LL<<50; long long sum[1<<25]; long long c[5][5]; void solve(int mask, long long cur) { if (sum[mask] != INF) return; sum[mask] = cur; if (mask == 0) { for (int i = 0; i < 25; i++) solve(mask | 1 << i, cur + c[i/5][i%5]); } else { for (int i = 0; i < 25; i++) { if (mask & 1 << i) continue; if ((i % 5 > 0) && (mask & 1 << (i-1)) || (i % 5 < 4) && (mask & 1 << (i+1)) || (i / 5 > 0) && (mask & 1 << (i-5)) || (i / 5 < 4) && (mask & 1 << (i+5))) { solve(mask | 1 << i, cur + c[i/5][i%5]); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { cin >> c[i][j]; } } fill(sum, sum + (1<<25), INF); solve(0, 0); long long ret = INF; int all = (1<<25) - 1; for (int mask = 0; mask <= all; mask++) { int nask = all ^ mask; if (sum[mask] != INF && sum[nask] != INF) ret = min(ret, abs(sum[mask] - sum[nask])); } cout << ret << endl; return 0; }