Submission #1326196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326196		repmann	Netrpeljivost (COI23_netrpeljivost)	C++20	0 / 100	1 ms	824 KiB

Main

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N;
int F[2049][2049];
ll DP[12][2049][2049], OPT[2049][2049], MIN[2049];
void DFS(int depth, int lc, int rc)
{
  if((rc - lc) == 1)
  {
    DP[depth][lc][rc] = DP[depth][rc][lc] = F[lc][rc];
    return;
  }
  int s = (lc + rc) >> 1, sl = (lc + s) >> 1, sr = (s + 1 + rc) >> 1;
  DFS(depth + 1, lc, s);
  DFS(depth + 1, s + 1, rc);
  for(int i = lc; i <= s; i++)
  {
    fill(OPT[i] + s + 1, OPT[i] + rc + 1, 1e18);
    for(int j = s + 1; j <= sr; j++)
    {
      for(int k = sr + 1; k <= rc; k++)
      {
        OPT[i][j] = min(F[i][k] + DP[depth + 1][k][j], OPT[i][j]);
        OPT[i][k] = min(F[i][j] + DP[depth + 1][j][k], OPT[i][k]);
      }
    }
  }
  for(int i = lc; i <= sl; i++)
  {
    for(int j = sl + 1; j <= s; j++)
    {
      for(int k = s + 1; k <= rc; k++)
      {
        DP[depth][i][k] = DP[depth + 1][i][j] + OPT[j][k];
        DP[depth][j][k] = DP[depth + 1][j][i] + OPT[i][k];
      }
    }
  }
  for(int i = lc; i <= s; i++)
  {
    for(int j = s + 1; j <= rc; j++) DP[depth][j][i] = DP[depth][i][j];
  }
  return;
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> N;
  for(int i = 1; i <= N; i++)
  {
    for(int j = 1; j <= N; j++) cin >> F[i][j];
  }
  if(N == 2) {cout << F[1][2] << '\n'; return 0;}
  int lc = 1, rc = N, s = (lc + rc) >> 1, sl = (lc + s) >> 1, sr = (s + 1 + rc) >> 1;
  for(int i = 0; (1 << i) <= N; i++)
  {
    for(int j = 1; j <= N; j++) fill(DP[i][j] + 1, DP[i][j] + N + 1, 1e18);
  }
  DFS(1, lc, s);
  DFS(1, s + 1, rc);
  fill(MIN + 1, MIN + N + 1, 1e18);
  for(int i = lc; i <= sl; i++)
  {
    for(int j = sl + 1; j <= s; j++)
    {
      MIN[j] = min(DP[1][i][j], MIN[j]);
      MIN[i] = min(DP[1][j][i], MIN[i]);
    }
  }
  for(int i = s + 1; i <= sr; i++)
  {
    for(int j = sr + 1; j <= rc; j++)
    {
      MIN[i] = min(DP[1][i][j], MIN[i]);
      MIN[j] = min(DP[1][j][i], MIN[j]);
    }
  }
  ll mn = 1e18;
  for(int i = lc; i <= s; i++)
  {
    for(int j = s + 1; j <= rc; j++) mn = min(MIN[i] + F[i][j] + MIN[j], mn);
  }
  cout << mn << '\n';

  return 0;
}

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