Submission #1316605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316605		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> l, r;
  ll mn;
};

node solve(ll s, ll e) {
  if (s == e)
    return {{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.l.size()) {
    lp(j, 0, b.l.size()) {
      c1 = min(c1, a.r[i] + b.l[j] + adj[s + i][mid + 1 + j]);
    }
  }
  lp(i, 0, b.l.size()) {
    lp(j, 0, a.l.size()) {
      c2 = min(c2, b.r[i] + a.l[j] + adj[mid + 1 + i][s + 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.l.size()) {
    res.l.push_back(a.l[i] + d1);
    res.r.push_back(a.r[i] + d2);
  }
  lp(i, 0, b.l.size()) {
    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;
    return 0;
  }
  cout << solve(0, n - 1).mn;
  return 0;
}

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