Submission #263193

#	Time	Username	Problem	Language	Result	Execution time	Memory
263193		vioalbert	Coins (LMIO19_monetos)	C++14	100 / 100	158 ms	49016 KiB

monetos

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rng(time(NULL));

const int N = 305, NN = 65, INF = 1e7;
int t, n, k1, k2, scale = 5;
int grid[N][N], pref[N][N];
int memo[NN][NN][NN*NN/2], opt[NN][NN][NN*NN/2];
int best[NN];

int dp(int idx, int prv, int total) {
	if(total < 0) return INF;
	if(idx == 0 && prv == n) return (total == 0)?0:INF;
	if(memo[idx][prv][total] != -1) return memo[idx][prv][total];
	int &ret = memo[idx][prv][total] = INF;
	if(idx > 0) {
		int goUp = min(INF, dp(idx - 1, prv, total - prv) + pref[idx][prv]);
		if(goUp != INF && ret > goUp) {
			ret = goUp;
			opt[idx][prv][total] = 1;
		}
	}
	if(prv < n) {
		int goRight = dp(idx, prv + 1, total);
		if(goRight != INF && ret > goRight) {
			ret = goRight;
			opt[idx][prv][total] = 2;
		}
	}
	return ret;
}

void backtrack() {
	int idx = n, prv = 0, total = n*n/2;
	while(idx > 0 || prv < n) {
		if(opt[idx][prv][total] == 1) {
			best[idx] = prv;
			idx--;
			total -= prv;
		} else if(opt[idx][prv][total] == 2) {
			prv++;
		}
	}
}

void compress() {
	for(int j = 1; j <= n; j++)
		pref[0][j] = 0;
	for(int i = 1; i <= n; i++) {
		pref[i][0] = 0;
		for(int j = 1; j <= n; j++)
			pref[i][j] = grid[i][j] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
	}

	n /= scale;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			int ii = i*scale, jj = j*scale;
			grid[i][j] = pref[ii][jj] - pref[ii - scale][jj] - pref[ii][jj - scale] + pref[ii - scale][jj - scale];
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> t >> n >> k1 >> k2;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++)
			cin >> grid[i][j];
	}

	if(t <= 2) scale = 1;
	compress();
	for(int j = 1; j <= n; j++)
		pref[0][j] = 0;
	for(int i = 1; i <= n; i++) {
		pref[i][0] = 0;
		for(int j = 1; j <= n; j++)
			pref[i][j] = pref[i][j - 1] + grid[i][j];
	}

	memset(memo, -1, sizeof memo);
	int ans = dp(n, 0, n*n/2);
	backtrack();
	n *= scale;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if(j <= best[(i + scale - 1) / scale] * scale) cout << 0 << " \n"[j == n];
			else cout << 1 << " \n"[j == n];
		}
	}

	return 0;
}

Compilation message (stderr)

monetos.cpp: In function 'int main()':
monetos.cpp:84:6: warning: unused variable 'ans' [-Wunused-variable]
   84 |  int ans = dp(n, 0, n*n/2);
      |      ^~~

• Subtask 1: 100 / 100