Submission #848364

#	Time	Username	Problem	Language	Result	Execution time	Memory
848364		patrikpavic2	Netrpeljivost (COI23_netrpeljivost)	C++17	100 / 100	474 ms	91152 KiB

Main

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 2050;
const int INF = 0x3f3f3f3f;

int n, cst[N][N];
ll dp[N][N];

int main(){
	scanf("%d", &n);
	for(int i = 0;i < n;i++) {
		for(int j = 0;j < n;j++) {
			scanf("%d", &cst[i][j]);
		}
	}
	for(int p = 1;p < n;p++) {
		int ch = p & (-p);
		for(int z = 0;z < n;z++) {
			dp[p][z] = (ll)1e18;
			int zz = (z ^ ch) & (~(ch - 1));
			for(int t = zz;t < zz + ch;t++)
				dp[p][z] = min(dp[p][z], dp[p - 1][t] + cst[t][z]);
		}
	}
	ll sol = (ll)1e18;
	for(int i = 0;i < n;i++)
		sol = min(sol, dp[n - 1][i]);
	printf("%lld\n", sol);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
Main.cpp:18:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |    scanf("%d", &cst[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~

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