제출 #1316602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316602		LIA	Netrpeljivost (COI23_netrpeljivost)	C++17	0 / 100	0 ms	332 KiB

Main

//
// Created by liasa on 29/01/2026.
//
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v vector
#define lp(i, s, e) for (ll i = s; i < e; ++i)

ll n;
ll adj[2050][2050];

struct node {
  v<ll> ind;
  v<ll> l, r;
};

node solve(ll s, ll e) {
  if (s == e)
    return {{s}, {0}, {0}};
  ll mid = (s + e) / 2;
  node a = solve(s, mid);
  node b = solve(mid + 1, e);
  ll c1 = 2e18, c2 = 2e18;
  lp(i, 0, a.ind.size()) {
    lp(j, 0, b.ind.size()) {
      c1 = min(c1, a.r[i] + b.l[j] + adj[a.ind[i]][b.ind[j]]);
    }
  }

  lp(i, 0, b.ind.size()) {
    lp(j, 0, a.ind.size()) {
      c2 = min(c2, b.r[i] + a.l[j] + adj[b.ind[i]][a.ind[j]]);
    }
  }

  node res;
  lp(i, 0, a.ind.size()) {
    res.ind.push_back(a.ind[i]);
    res.l.push_back(a.l[i]);
    res.r.push_back(a.r[i] + c2);
  }
  lp(i, 0, b.ind.size()) {
    res.ind.push_back(b.ind[i]);
    res.l.push_back(b.l[i]);
    res.r.push_back(b.r[i] + c1);
  }
  if (res.ind.size() == n) {
    ll min_ar = 2e18, min_br = 2e18;
    for (ll x : a.r)
      min_ar = min(min_ar, x);
    for (ll x : b.r)
      min_br = min(min_br, x);
    cout << min(c1 + min_br, c2 + min_ar) << endl;
  }

  return res;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  lp(i, 0, n) {
    lp(j, 0, n) { cin >> adj[i][j]; }
  }
  if (n == 1) {
    cout << 0 << endl;
    return 0;
  }
  solve(0, n - 1);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 17
• Subtask 3: 0 / 32
• Subtask 4: 0 / 41