제출 #1316603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316603		LIA	Netrpeljivost (COI23_netrpeljivost)	C++17	0 / 100	1 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;
  ll mn;
};
node solve(ll s, ll e) {
  if (s == e)
    return {{s}, {0}, {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;
  res.mn = a.mn + b.mn + min(c1, c2);
  ll d1 = c1 - min(c1, c2);
  ll d2 = c2 - min(c1, c2);
  lp(i, 0, a.ind.size()) {
    res.ind.push_back(a.ind[i]);
    res.l.push_back(a.l[i] + d1);
    res.r.push_back(a.r[i] + d2);
  }
  lp(i, 0, b.ind.size()) {
    res.ind.push_back(b.ind[i]);
    res.l.push_back(b.l[i] + d2);
    res.r.push_back(b.r[i] + d1);
  }

  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;
  }
  cout << solve(0, n - 1).mn << endl;
}

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