글 읽기 - 왜틀릴까요..

shjohw12 2년 전 0

어디가 잘못 됐을까요..?
#include<bits/stdc++.h>
#define int ll
#define sz(x) int((x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using pi = pair<int,int>;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int minf = 0xc0c0c0c0c0c0c0c0;

char A[305][305];
bool dp[305][305][305];
// 0 : 위
// 1 : 아래
// 2 : 왼쪽
// 3 : 오른쪽
int v[305][305][4];

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n,m; cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>(A[i]+1);

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            // 위
            v[i][j][0] = (v[i-1][j][0] << 1) | (A[i][j] - '0');

            // 왼
            v[i][j][2] = (v[i][j-1][2] << 1) | (A[i][j] - '0');
        }
    }


    for (int i=n; i>=1; i--) {
        for (int j=m; j>=1; j--) {
            // 아래
            v[i][j][1] = (v[i+1][j][1] << 1) | (A[i][j] - '0');

            // 오른
            v[i][j][3] = (v[i][j+1][3] << 1) | (A[i][j] - '0');
        }
    }

    int res = -1;

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            dp[i][j][0] = dp[i][j][1] = 1;

            for (int k=2; k<=min(i,j); k++) {
                if (!dp[i-1][j-1][k-2]) continue;

                // v[i][j][2]

                // v[i-k+1][j-k+1][3]

                bool ok = 1;

                for (int left = j-k+1, right = j; left<=right;) {
                    int x = v[i][right][2], y = v[i-k+1][left][3];


                    if (right - left < 63) {
                        int t = right - left + 1;
                        x &= ((1LL<<t) - 1);
                        y &= ((1LL<<t) - 1);
                    }

                    if (x != y) {
                        ok = 0;
                        break;
                    }

                    left += 64;
                    right -= 64;
                }

                if (!ok) continue;

                // v[i][j][0]

                // v[i-k+1][j-k+1][1]

                for (int lo=i-k+1, hi=i; lo<=hi;) {
                    int x = v[hi][j][0], y = v[lo][j-k+1][1];

                    if (hi - lo < 63) {
                        int t = hi - lo + 1;
                        x &= ((1LL<<t) - 1);
                        y &= ((1LL<<t) - 1);
                    }

                    if (x != y) {
                        ok = 0;
                        break;
                    }

                    lo += 64;
                    hi -= 64;
                }

                if (ok) {
                    dp[i][j][k] = 1;
                    res = max(res, k);
                }
            }
        }
    }

    cout<<res<<'\n';

    return 0;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

왜틀릴까요..

shjohw12 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
