oj.uz

답안 #1026770

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1026770 2024-07-18T10:55:07 Z vjudge1 Netrpeljivost (COI23_netrpeljivost) C++17
0 / 100
 1 ms 2396 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define OYY LLONG_MAX
#define mod 998244353
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define lim 513
#define fi first
#define se second

int n;

int dizi[lim][lim];

int dp[lim][lim];

int32_t main(){
	faster
	cin>>n;
	
	FOR{
		for(int j=1;j<=n;j++){
			cin>>dizi[i][j];
			dp[i][j]=INT_MAX;
		}
	}
	
	for(int i=1;i<=n;i+=2){
		dp[i][i+1]=dizi[i][i+1];
		dp[i+1][i]=dizi[i+1][i];
	}
	
	vector<int> v;
	vector<int> v2;
	
	v.push_back(1);
	v.push_back(2);
	
	int tut=3;
	
	FOR{
		if(v.size()==n)break;
		
		while(v2.size()<v.size()){
			v2.push_back(tut);
			tut++;
		}
		
		/*cout<<i<<endl;
		
		for(auto x:v){
			cout<<x<<" ";
		}
		cout<<endl;
		for(auto x:v2){
			cout<<x<<" ";
		}		
		cout<<endl;*/
		for(int j=0;j<v.size();j++){
			for(int k=0;k<v2.size();k++){
				int left=v[j],r=v2[k];
				dp[left][r]=INT_MAX;
				
				//cout<<left<<" "<<r<<endl;
				
				for(int l=0;l<v.size();l++){
					if((v[l]-1)/(v.size()/2)!=(left)/(v.size()/2)){
						for(int o=0;o<v2.size();o++){
							if((v2[o]-1)/(v.size()/2)!=(r-1)/(v.size()/2)){
								dp[left][r]=min(dp[left][r],dp[left][v[l]]+dp[v2[o]][r]+dizi[v[l]][v2[o]]);
							}
						}
					}
				}
			}
		}
		
		for(int j=0;j<v2.size();j++){
			for(int k=0;k<v.size();k++){
				int left=v2[j],r=v[k];
				
				for(int l=0;l<v2.size();l++){
					if((v2[l]-1)/(v.size()/2)!=(left)/(v.size()/2)){
						for(int o=0;o<v.size();o++){
							if((v[o]-1)/(v.size()/2)!=(r-1)/(v.size()/2)){
								dp[left][r]=min(dp[left][r],dp[left][v2[l]]+dp[v[o]][r]+dizi[v2[l]][v[o]]);
								//cout<<dpdp[left][r]<<endl;
							}
						}
					}
				}
			}
		}
		
		for(auto x:v2){
			v.push_back(x);
		}
		
		v2.clear();
		
	}
	
	int cev=LLONG_MAX;
	
	/*FOR{
		for(int j=1;j<=n;j++){
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}*/
	
	for(int i=1;i<=n/2;i++){
		for(int j=n/2+1;j<=n;j++){
			cev=min(cev,dp[i][j]);
		}
	}
	
	for(int i=n/2+1;i<=n;i++){
		for(int j=1;j<=n/2;j++){
			cev=min(cev,dp[i][j]);
		}
	}
	
	cout<<cev<<'\n';
	
	return 0;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:47:14: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   47 |   if(v.size()==n)break;
      |      ~~~~~~~~^~~
Main.cpp:64:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int j=0;j<v.size();j++){
      |               ~^~~~~~~~~
Main.cpp:65:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    for(int k=0;k<v2.size();k++){
      |                ~^~~~~~~~~~
Main.cpp:71:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int l=0;l<v.size();l++){
      |                 ~^~~~~~~~~
Main.cpp:73:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |       for(int o=0;o<v2.size();o++){
      |                   ~^~~~~~~~~~
Main.cpp:83:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for(int j=0;j<v2.size();j++){
      |               ~^~~~~~~~~~
Main.cpp:84:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |    for(int k=0;k<v.size();k++){
      |                ~^~~~~~~~~
Main.cpp:87:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int l=0;l<v2.size();l++){
      |                 ~^~~~~~~~~~
Main.cpp:89:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |       for(int o=0;o<v.size();o++){
      |                   ~^~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -