제출 #1026583

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

Main

#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define int long long int
#define endl '\n'
#define N 2050
#define M 15
#define big 2147483647 
#define bigg 9223372036854775807 
#define pb push_back
#define p push
#define ins insert
#define f first
#define s second
int dp[N][N],arr[N][N];
int nnn;
vector<pair<int,int>>  hesap(int l,int r){
	vector<pair<int,int>> cev;

	//cout<<l<<" "<<r<<endl;
	if(r<l)return cev;
	if(l==r){		
		dp[l][r]=dp[r][l]=0;
		cev.pb({l,r});
		cev.pb({r,l});
		return cev;
	}
	int mid=(l+r)/2;
	vector<pair<int,int>> a=hesap(l,mid), b=hesap(mid+1,r);
	int mn=bigg;
	for(auto u:a){
		int x=u.f, y=u.s;
		for(auto v:b){
			int m=v.f,n=v.s;
			int top=dp[x][y]+dp[m][n];
			int yes=arr[y][m], ok=arr[x][n];
			if(dp[x][n]==-1){
				dp[x][n]=top+yes;
				cev.pb({x,n});
				cev.pb({n,x});
			}
			dp[x][n]=min(dp[x][n],top+yes);
			dp[n][x]=dp[x][n];

			if(dp[y][m]==-1){
				dp[y][m]=top+ok;
				cev.pb({y,m});
				cev.pb({m,y});
			}
			dp[y][m]=min(dp[y][m],top+yes);
			dp[m][y]=dp[y][m];
			//cout<<x<<" "<<y<<"  "<<m<<" "<<n<<": "<<dp[x][n]<<" "<<dp[m][y]<<" _ "<<ok<<" "<<yes<<" "<<top<<endl;
			mn=min(mn,min(dp[x][n],dp[m][y]));
		}
	}
	if(l==1&&r==nnn){
		cout<<mn<<" "<<endl;
	}
	return cev;

}
signed main(){
  	lalala;
  	memset(dp,-1,sizeof(dp));
  	cin>>nnn;
  	for(int i=1;i<=nnn;i++){
  		for(int j=1;j<=nnn;j++)cin>>arr[i][j];
  	}
  	hesap(1,nnn);



}

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