結果

問題 No.861 ケーキカット
コンテスト
ユーザー 梧桐
提出日時 2026-06-19 17:56:36
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 1,830 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 572 ms
コンパイル使用メモリ 90,744 KB
実行使用メモリ 16,768 KB
最終ジャッジ日時 2026-06-19 17:57:01
合計ジャッジ時間 5,621 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int Calc(int, int)':
main.cpp:25:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   25 |         auto [xx, yy] = q.front(); q.pop();
      |              ^

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 10;
const LL INF = 9e18;

LL ans;
queue<PII> q;
bool st[N][N];
int a[N][N], col[N][N], dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };

int Calc(int x, int y) {
    memset(st, 0, sizeof(st));
    int ret = 0;
    q.push({ x, y });
    st[x][y] = true;
    while (!q.empty()) {
        auto [xx, yy] = q.front(); q.pop();
        ++ret;
        for (int i = 0; i < 4; ++i) {
            int nx = xx + dx[i], ny = yy + dy[i];
            if (1 <= nx && nx <= 5 && 1 <= ny && ny <= 5 && col[nx][ny] == col[x][y] && !st[nx][ny]) {
                q.push({ nx, ny });
                st[nx][ny] = true;
            }
        }
    }
    return ret;
}

int main() {
    // freopen("cake.in", "r", stdin);
    // freopen("cake.out", "w", stdout);

    for (int i = 1; i <= 5; ++i) {
        for (int j = 1; j <= 5; ++j) {
            scanf("%d", &a[i][j]);
        }
    }

    ans = INF;
    for (int mask = 1; mask < (1 << 25) - 1; ++mask) {
        LL sum1 = 0LL, sum2 = 0LL;
        int x1, y1, x2, y2;
        x1 = y1 = x2 = y2 = 0;
        for (int i = 1; i <= 5; ++i) {
            for (int j = 1; j <= 5; ++j) {
                if (mask >> (5 * (i - 1) + j - 1) & 1) {
                    col[i][j] = 1;
                    x1 = i, y1 = j;
                    sum1 += a[i][j];
                } else {
                    col[i][j] = 2;
                    sum2 += a[i][j];
                    x2 = i, y2 = j;
                }
            }
        }
        int cnt = 0;
        cnt += Calc(x1, y1);
        cnt += Calc(x2, y2);
        if (cnt == 25) {
            ans = min(ans, llabs(sum1 - sum2));
        }
    }

    printf("%lld\n", ans);

    return 0;
}
0