Submission #919298

#	Time	Username	Problem	Language	Result	Execution time	Memory
919298		TIN	Domino (COCI15_domino)	C++17	30 / 160	805 ms	314508 KiB

domino

#include <bits/stdc++.h>

using namespace std;

#define FNAME "test"

#define int long long

const int N = 2005;

int n, k;
int grid[N][N];
int sum = 0;
vector<vector<vector<int>>> dp, mx, pmx, t;

void Task() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cout << fixed << setprecision(9);
	if (fopen(FNAME".inp","r")) {
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

void Solve() {
	//Your Code
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> grid[i][j];
			sum += grid[i][j];
		}
	}
	dp.resize(2, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));
	mx.resize(2, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));
	pmx.resize(2, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));
	t.resize(2, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));
	for (int dom = 1; dom <= k; dom++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == 1 && j == 1) continue;
				// (i - 1, j) -> (i, j)
				dp[0][i][j] = max(pmx[0][i][j - 1], pmx[1][i][j - 1]);
				if (i - 2 >= 0) dp[0][i][j] = max(pmx[0][i - 2][j], pmx[1][i - 2][j]);
				dp[0][i][j] += grid[i - 1][j] + grid[i][j];
				mx[0][i][j] = max(dp[0][i][j], max(mx[0][i - 1][j], mx[0][i][j - 1]));
				// (i, j - 1) -> (i, j)
				dp[1][i][j] = max(pmx[0][i - 1][j], pmx[1][i - 1][j]);
				if (j - 2 >= 0) dp[1][i][j] = max(pmx[0][i][j - 2], pmx[1][i][j - 2]);
				dp[1][i][j] += grid[i][j - 1] + grid[i][j];
				mx[1][i][j] = max(dp[1][i][j], max(mx[1][i - 1][j], mx[1][i][j - 1]));
			}
		}
		pmx = mx;
		mx = t;
	}
	int res = sum - max(pmx[0][n][n], pmx[1][n][n]);
	cout << res << '\n';
}

signed main() {
	Task();
	Solve();
	cerr << "\nTime run: " << 1000*clock()/CLOCKS_PER_SEC << "ms";
	return 37^37;
}

Compilation message (stderr)

domino.cpp: In function 'void Task()':
domino.cpp:21:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   freopen(FNAME".inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
domino.cpp:22:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   freopen(FNAME".out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10
• Subtask 16: 0 / 10