Submission #1028570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028570		TrieTr	Netrpeljivost (COI23_netrpeljivost)	C++14	100 / 100	1197 ms	164608 KiB

Main

#include<bits/stdc++.h>
using namespace std;

void local() {
    #define taskname ""
    if (fopen(taskname".inp", "r")) {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
}

#define ll long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

template<class X, class Y> bool mini(X &a, const Y &b) {return (a > b) ? a = b, true : false;}
template<class X, class Y> bool maxi(X &a, const Y &b) {return (a < b) ? a = b, true : false;}

const int N = 3e3 + 5;

int n;
ll a[N][N];

namespace sub1 {
	bool check() {
		return n <= 16;
	}
	ll solve(int st, int en, int l, int r) {
		int mid = (l + r) >> 1;
		if((st <= mid && en <= mid) || (st > mid && en > mid)) return 1e18;
		if(r - l == 1) {
			return a[st][en];
		}
		ll res = 1e18;
		for(int i = l; i <= mid; i++) {
			for(int j = mid + 1; j <= r; j++) {
				if(st <= mid) {
					mini(res, a[i][j] + solve(st, i, l, mid) + solve(j, en, mid + 1, r));
				}
				else {
					mini(res, a[i][j] + solve(st, j, mid + 1, r) + solve(i, en, l, mid));
				}
			}
		}
		return res;
	}
	void solve() {
		ll res = 1e18;
	    for(int i = 1; i <= n / 2; i++) {
	    	for(int j = n / 2 + 1; j <= n; j++) {
	    		mini(res, solve(i, j, 1, n));
	    		mini(res, solve(j, i, 1, n));
	    	}
	    }
	    cout << res;
	}
}
namespace sub4 {
	ll dp[N][N], cur[N][N];
	void solve(int l, int r) {
		if(r - l == 1) {
			dp[l][r] = dp[r][l] = a[l][r];
			return;
		}
		int mid = (l + r) >> 1, mid1 = (l + mid) >> 1, mid2 = (mid + 1 + r) >> 1;
		solve(l, mid); solve(mid + 1, r);
		for(int i1 = l; i1 <= mid1; i1++) {
			for(int i2 = mid1 + 1; i2 <= mid; i2++) {
				for(int j = mid + 1; j <= r; j++) {
					mini(cur[i1][j], dp[i1][i2] + a[i2][j]);
					mini(cur[i2][j], dp[i1][i2] + a[i1][j]);
				}
			}
		}
		for(int i = l; i <= mid; i++) {
			for(int j1 = mid + 1; j1 <= mid2; j1++) {
				for(int j2 = mid2 + 1; j2 <= r; j2++) {
					mini(dp[i][j1], cur[i][j2] + dp[j1][j2]);
					mini(dp[i][j2], cur[i][j1] + dp[j1][j2]);
				}
			}
		}
	}
	void solve() {
		ll res = 1e18;
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				dp[i][j] = 1e18;
				cur[i][j] = 1e18;
			}
		}
		for(int i = 1; i <= n; i++) a[i][i] = 1e18;
		solve(1, n);
	    for(int i = 1; i <= n / 2; i++) {
	    	for(int j = n / 2 + 1; j <= n; j++) {
	    		mini(res, dp[i][j]);
	    	}
	    }
	    cout << res;
	}
}


int main() {
    fastio; local();
    cin >> n;
    for(int i = 1; i <= n; i++) {
    	for(int j = 1; j <= n; j++) {
    		cin >> a[i][j];
    	}
    }
    sub4::solve();
}

Compilation message (stderr)

Main.cpp: In function 'void local()':
Main.cpp:7:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:8:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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