제출 #1189412

#제출 시각아이디문제언어결과실행 시간메모리
1189412mychecksedadNetrpeljivost (COI23_netrpeljivost)C++20
0 / 100
228 ms589824 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 3000+100, M = 1e5+10, K = 52, MX = 30; const ll INF = 1e18; int n; ll c[N][N]; vector<ll> dp[N*4][N]; void f(int l, int r, int v){ for(int i = 1; i <= r - l + 1; ++i) dp[v][i].resize(r - l + 2, INF); if(l == r){ dp[v][1][1] = 0; return; } int mid = l+r>>1; f(l, mid, v<<1); f(mid+1, r, v<<1|1); int S = mid - l + 1; for(int x = 1; x <= mid - l + 1; ++x){ for(int y = 1; y <= mid - l + 1; ++y){ for(int X = 1; X <= r - mid; ++X){ for(int Y = 1; Y <= r - mid; ++Y){ dp[v][x][Y + S] = min(dp[v][x][Y + S], dp[v<<1][x][y] + dp[v<<1|1][X][Y] + c[l - 1 + y][l - 1 + X + S]); dp[v][X + S][y] = min(dp[v][X + S][y], dp[v<<1][x][y] + dp[v<<1|1][X][Y] + c[l - 1 + x][l - 1 + Y + S]); } } } } } void solve(){ cin >> n; for(int i = 1; i <= n; ++i){ for(int j = 1; j <= n; ++j) cin >> c[i][j]; } f(1, n, 1); ll ans = INF; for(int i = 1; i <= n; ++i){ for(int j = 1; j <= n; ++j) ans = min(ans, dp[1][i][j]); } cout << ans; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...