#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++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
