제출 #1365801

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1365801		domi	Netrpeljivost (COI23_netrpeljivost)	C++20	100 / 100	404 ms	66348 KiB

Main

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 2048;
const int INF = 1e16;

using namespace std;

int dp[NMAX + 5][NMAX + 5], cost[NMAX + 5][NMAX + 5], n;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            cin >> cost[i][j];
    }

    fill(&dp[0][0], &dp[0][0] + (NMAX + 5) * (NMAX + 5), INF);
    fill(dp[0], dp[0] + n, 0LL);
    for (int x = 0; x < n - 1; ++x) {
        int ones = __builtin_ctz(x + 1);
        for (int v = 0; v < n; ++v) {
            for (int xr = 0; xr < (1LL << ones); ++xr) {
                int nv = (v ^ xr ^ (1LL << ones));
                dp[x + 1][nv] = min(dp[x + 1][nv], dp[x][v] + cost[v][nv]);
            }
        }
    }

    cout << *min_element(dp[n - 1], dp[n - 1] + n) << '\n';
    return 0;
}

• 서브태스크 1: 10 / 10
• 서브태스크 2: 17 / 17
• 서브태스크 3: 32 / 32
• 서브태스크 4: 41 / 41