Submission #1114262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114262		epicci23	Netrpeljivost (COI23_netrpeljivost)	C++17	59 / 100	411 ms	13392 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int INF = 1e18;
const int N = 520;

int cost[N][N],dp[N][N],pre[N][N];

void f(int l,int r){
  
  if(l+1==r){
    dp[l][l]=dp[r][r]=0;
    dp[l][r]=dp[r][l]=cost[l][r];
    return;
  }

  int m=(l+r)/2;
  f(l,m),f(m+1,r);
   
  int col[N];
  for(int i=l;i<=r;i++){
    if(i<=m) col[i]=0;
    else col[i]=1;
  }

  for(int b=l;b<=r;b++)
    for(int c=l;c<=r;c++)
      for(int d=l;d<=r;d++){
      	if(col[b]==col[c]) continue;
        if(col[c]==col[d]) continue;
        if(col[b]!=col[d]) continue;
  	    if(d==c || d==b || b==c) continue;
      	pre[b][c]=min(pre[b][c], dp[d][b] + cost[c][d]);
      }

  for(int a=l;a<=r;a++){
  	for(int b=l;b<=r;b++){
  	  if(col[a]==col[b]) continue;
  	  for(int c=l;c<=r;c++){
  	  	if(c==a || c==b || a==b) continue;
  	  	if(col[a] != col[c]) continue;
  	  	dp[a][b] = min(dp[a][b], dp[a][c] + pre[b][c]);
  	  }
  	}
  }

  for(int a=l;a<=r;a++) 
    for(int b=l;b<=r;b++) 
      if(col[a]==col[b]){
       dp[b][a]=dp[a][b]=INF;
       pre[a][b]=pre[b][a]=INF;
      }
}

void _(){
  int n;
  cin >> n;
  
  for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) pre[i][j]=dp[i][j]=INF;
  	
  for(int i=1;i<=n;i++){
  	for(int j=1;j<=n;j++){
  	  cin >> cost[i][j];
  	}
  }
  
  f(1,n);
  int ans=INF;
  for(int i=1;i<=n;i++){
  	for(int j=1;j<=n;j++){
      if(i<=n/2 && j<=n/2) continue;
      if(i>n/2 && j>n/2) continue;
  	  ans=min(ans,dp[i][j]);
  	}
  }

  cout << ans << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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