제출 #1129797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129797		crafticat	Table Tennis (JOI24_tabletennis)	C++20	0 / 100	1 ms	324 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define F0R(i, n) for (int i = 0; i < n;i++)
#define FOR(i,j, n) for (int i = j; i < n;i++)

template<typename T>
using V = vector<T>;
using vi = V<int>;

vi dp;

V<V<bool>> g;

void connect(int l, int r, int l2, int r2) {
    FOR(i, l, r) {
        FOR(j, l2, r2) {
            g[i][j] = 1;
            g[j][i] = 0;
        }
    }
}

void solve(int startI, int N, int k) {
    if (k == 0) return;
    FOR(j, 1, N) {
        if (dp[j] + dp[N - j] >= k) {
            // Do this
            solve(startI, j,min(dp[j], k));
            solve(startI + j, N - j, k - min(dp[j], k));

            connect(startI + j, startI + N,startI, startI + j);
            return;
        }
    }

    FOR(j, 1, N) {
        FOR(t, 1, N) {
            if (j + t >= N) continue;

            if (dp[t] + dp[j] + dp[N - j - t] + j * t * (N - j - t) >= k and j * t * (N - j - t) <= k) {
                // Split 3
                k -= j * t * (N - j - t);
                solve(startI, j, min(k, dp[j]));
                solve(startI + j, t, min(k - min(k, dp[j]), dp[t]));
                solve(startI + j + t, N - j - t, k - min(k - min(k, dp[j]), dp[t]));

                connect(startI + j + t, startI + N,startI + j, startI + j + t); //
                connect(startI + j, startI + j + t,startI, startI + j); //
                connect(startI, startI + j,startI + j + t, startI + N); //
                return;
            }
        }
    }
    exit(5);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int q; cin >> q;


    F0R(test, q) {
        int n, K; cin >> n >> K;
        dp.clear();
        dp.resize(n + 1);

        FOR(i, 1, n + 1) {
            F0R(j, i) {
                dp[i] = max(dp[i], dp[j] + dp[i - j]);
            }
            FOR(j, 1, i) {
                FOR(k, 1, i) {
                    if (j + k >= i) continue;

                    dp[i] = max(dp[i], dp[k] + dp[j] + dp[i - j - k] + j * k * (i - j - k));
                }
            }
        }

        g.clear();
        g.resize(n,V<bool>(n));

        if (dp[n] >= K) {
            cout << "YES\n";
            solve(0, n, K);
            F0R(i,n) {
                F0R(j, n) {
                    if (i <= j) continue;
                    cout << (g[i][j] ? '1': '0') << "";
                }
                cout << "\n";
            }
        } else {
            cout << "NO\n";
        }
    }


    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 4
• Subtask 3: 0 / 23
• Subtask 4: 0 / 30
• Subtask 5: 0 / 15
• Subtask 6: 0 / 23